参考博客 https://blog.csdn.net/clover_hxy/article/details/50683832关于欧拉定理推论的证明 https://www.cnblogs.com/aseer/p/9675610.html/*
给定A,B,C,C是质数，求出A^x=B(mod C)的解
解：A^x = A^(x % phi[C]) = B(mod C) (欧拉定理推论)
x % phi[C] < C
所以不超过C的范围内必有一个解，
只要求到C即可，
进行分块，另 m=sqrt(C),向上取整,
那么 x=i*m-j
原式==》A^j*B = A^(m*i)(mod C)
先枚举j，将A^j*B进行hash
再枚举i，从hash表中找到第一个满足条件的A^j*B
此时x=i*m-j
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define ll long long
ll a,b,c,m,f[10000000];
map<ll,
int>
mp;
ll Pow(ll x){
ll res=
1,aa=
a;
while(x>
0){
if(x%
2)
res=res*aa%
c;
x>>=
1;
aa=aa*aa%
c;
}
return res;
}
int main(){
while(scanf(
"%lld%lld%lld",&c,&a,&b)!=
EOF){
mp.clear();
if(a%c==
0){
//c|a,显然是不存在解x的，除非
puts(
"no solution");
continue;
}
int p=
0;
m=ceil(sqrt(c*
1.0));
ll ans;
for(
int j=
0;j<=m;j++){
//预处理所有j的情况，建立hash表
if(j==
0){
ans=b%c;mp[ans]=j;
continue;
}
ans=(ans*a)%
c;
mp[ans]=
j;
}
ll t=
Pow(m);
ans=
1;
for(
int i=
1;i<=m;i++
){
ans=(ans*t)%
c;
if(mp[ans]){
//枚举每个块ans=a^(m*i)=a^j*b,把hash表中的那个j找到即可
int t=i*m-
mp[ans];
printf("%d\n",(t%c+c)%
c);
p=
1;
break;
}
}
if(!
p)
puts("no solution");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10440760.html
相关资源：DirectX修复工具V4.0增强版
