http://cogs.pro/cogs/problem/problem.php?pid=1265
★☆ 输入文件：mod.in 输出文件：mod.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
【输入格式】
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
【输出格式】
输出只有一行，包含一个正整数X0，即最小正整数解。输入数据保证一定有解。
【样例输入】
3 10
【样例输出】
7
【数据范围】
对于 40%的数据，2 ≤b≤ 1,000；
对于 60%的数据，2 ≤b≤ 50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,000。
欧拉定理求解，要mod b才可以计算出最小值
欧拉定理：a ^φ(p) ≡ 1(mod p) 对于任意互质的 a,p 恒成立. -->>a × a^( φ(p)−1) ≡ 1(mod p)
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 #define LL long long 7 LL a,b; 8 9 LL phi(LL x) 10 { 11 LL ret=1; 12 for(LL i=2;i*i<=x;i++) 13 if(x%i==0) 14 { 15 x/=i; 16 ret*=i-1; 17 for(;x%i==0;) 18 ret*=i,x/=i; 19 } 20 if(x>1) ret*=x-1; 21 return ret; 22 } 23 LL Q_pow(LL a,LL b,LL mod) 24 { 25 LL ret=1,base=a; 26 for(;b;b>>=1) 27 { 28 if(1&b) ret=(ret*base)%mod; 29 base=(base*base)%mod; 30 } 31 return ret; 32 } 33 34 int main() 35 { 36 freopen("mod.in","r",stdin); 37 freopen("mod.out","w",stdout); 38 39 scanf("%lld%lld",&a,&b); 40 LL ans=Q_pow(a,phi(b)-1,b); 41 for(;ans<0;) ans+=b; 42 printf("%lld",ans); 43 return 0; 44 }