题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2242
题意：给出 a,b,p, 分别求：
求\(a^b \ mod \ p\)
求最小的非负整数 x 满足 \(a\cdot x\equiv b \ (\ mod\ p \ )\)。
求最小的非负整数 x 满足 \(a^x\equiv b \ (\ mod\ p \ )\)。
这题数据强一点吧... 爆 long long 会死的很惨 ...
有一个没啥用的小优化，发现 p 不一定是质数，每次枚举上界处理到 phi(p) 即可，但是由于要暴力求 phi(p) 反而会变慢一点...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#include <map> #include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 100000 #define ll long long using namespace std; char xB[1<<15],*xS=xB,*xT=xB; #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,k; int a,b,p; int quickmod(int a,int b) { int ret=1; while(b) { if(b&1)ret=(ll)ret*a%p; b>>=1,a=(ll)a*a%p; } return ret; } namespace subtask1 { void main() { while(T--) { a=read(),b=read(),p=read(); printf("%d\n",quickmod(a,b)); } } } namespace subtask2 { inline int gcd(int a,int b) {return b==0?a:gcd(b,a%b);} int x,y; void exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return ; } exgcd(b,a%b,x,y); int tmp=x; x=y,y=tmp-a/b*y; return ; } void main() { while(T--) { a=read(),b=read(),p=read(); int k=gcd(a,p); if(b%k) { puts("Orz, I cannot find x!"); continue ; } a/=k,p/=k; exgcd(a,p,x,y); x=(ll)x*b%p; printf("%d\n",(x+p)%p); } } } namespace subtask3 { map<int,int> f; int phi(int x) { int ret=x; for(int i=2;i*i<=x;i++) if(x%i==0) { ret-=ret/i; while(x%i==0)x/=i; } if(x>1)ret-=ret/x; return ret; } void main() { while(T--) { a=read(),b=read(),p=read(); a%=p,b%=p; if(!a&&!b){puts("1");continue ;} if(!a){puts("Orz, I cannot find x!");continue ;} bool flag=0; f.clear(); int m=ceil(sqrt(phi(p))); int bas=quickmod(a,m),pos=b; for(int j=0;j<=m;j++) { if(j!=0)pos=(ll)pos*a%p; f[pos]=j; } pos=bas; for(int i=1;i<=m;i++,pos=(ll)pos*bas%p) if(f.count(pos)) { flag=1; printf("%d\n",i*m-f[pos]); break ; } if(!flag) puts("Orz, I cannot find x!"); } } } int main() { T=read(),k=read(); if(k==1)subtask1::main(); if(k==2)subtask2::main(); if(k==3)subtask3::main(); } |
Comments | NOTHING