一般形式
求解同余方程x^n\equiv y (\mod p),(x,p)=1
将n进行拆分,设n=s*m-k,有x^{s*m}=y*x^k (\mod k),其中1\leq s \leq m+1,0\leq k
枚举等式右边,扔到map里保存起来.然后再枚举等式左边,检测map中是否有存值.如果有,即为方程的最小解.
时间复杂度为m+\frac{p}{m},显然,m=\sqrt{p}时最优.
广义形式
设d=(x,p).若y\%d!=0的话,原方程显然无解.如果有解,方程变形为\frac{x}{d}*x^{n-1}\equiv \frac{y}{d} (\mod \frac{p}{d})
重复以上过程,直到x与p互质,得到\frac{x^k}{D}*x^{n-k}\equiv \frac{y}{D} (\mod \frac{p}{D})
类比于一般形式的方程求解即可,前面只需添加一个系数,以及答案要加上一个k
例题
多少个1
求最小的n,使其满足
\frac{10^n-1}{9}\equiv k (\mod p)
p为质数
直接求解即可,注意对2和5进行特判
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL k,m;
vector <LL> Ans;
map <LL,LL> M;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline __int128 Mi(__int128 x,__int128 y,__int128 MOD){
__int128 p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline void BSGS(LL x,LL y,LL p){
register int i=0;
__int128 s=0,t=0,m=(__int128)sqrt(p)+1;
s=y;
for (i=0;i<=m;i++) M[s]=i,s=s*x%p;
t=s=Mi(x,m,p);
for (i=1;i<=m+1;i++){
if (M[s]) Ans.push_back(i*m-M[s]);
s=s*t%p;
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%lld%lld",&k,&m);
if (m==2||m==5){
printf("1\n"); return 0;
}
BSGS(10,(9*k+1)%m,m);
sort(Ans.begin(),Ans.end());
printf("%lld\n",Ans[0]);
return 0;
}
Ex_BSGS模板
求解同余方程x^n\equiv y (\mod p)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
using namespace std;
LL k,m,x,y,p;
map <LL,LL> M;
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline LL Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}
inline LL Mi(LL x,LL y,LL MOD){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline LL Ex_BSGS(LL x,LL y,LL p){
register LL i=0,sum=1,s=1,m=0,k=0;
M.clear();
if (y==1) return 0;
while ((s=Gcd(x,p))!=1){
if (y%s) return -1;
sum=sum*(x/s)%p;
y/=s; p/=s; k++;
if (y==sum) return k;
}
m=(LL)sqrt(p)+1;
for (i=0;i<=m;i++) M[y]=i,y=y*x%p;
s=Mi(x,m,p); y=s*sum%p;
for (i=1;i<=m+1;i++){
if (M[y]) return k+i*m-M[y];
y=y*s%p;
}
return -1;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
while (1){
x=read(); p=read(); y=read();
if (x+y+p==0) return 0;
p=Ex_BSGS(x,y,p);
printf((p==-1)?"No Solution\n":"%lld\n",p);
}
return 0;
}
[SDOI2011]计算器
实现一个计算器,支持计算快速幂,逆元和解高次同余方程.
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL T,k,y,z,p,x;
map <LL,LL> M;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline int Gcd(LL a,LL b){return (!b)?a:Gcd(b,a%b);}
inline LL Mi(LL x,LL y,LL MOD){
LL p=x,t=1,Res=1;
for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
return Res;
}
inline void Ex_gcd(LL a,LL b,LL &x,LL &y){
LL p=0,q=0;
if (b==0) {
x=1; y=0; return;
} else {
Ex_gcd(b,a%b,p,q);
x=q; y=p-a/b*q;
}
}
inline int Inv(LL a,LL p){
LL x=0,y=0;
Ex_gcd(a,p,x,y);
return x;
}
inline LL Ex_BSGS(LL x,LL y,LL p){
LL sum=1,m=0,s=1,k=0,i=0;
M.clear();
if (y==1) return 0;
while ((s=Gcd(x,p))!=1){
if (y%s) return -1;
y/=s; p/=s;
sum=sum*x/s%p; k++;
if (y==sum) return k;
}
m=(LL)sqrt(p)+1;
for (i=0;i<=m;i++) M[y]=i,y=y*x%p;
s=Mi(x,m,p); sum=sum*s%p;
for (i=1;i<=m+1;i++){
if (M[sum]) return i*m-M[sum]+k;
sum=sum*s%p;
}
return -1;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read(); k=read();
while (T--){
y=read(); z=read(); p=read();
if (k==1) printf("%lld\n",Mi(y,z,p));
else if (k==2)
(Gcd(y,p)>1)?printf("Orz, I cannot find x!\n"):printf("%lld\n",(Inv(y,p)+p)*z%p);
else {
x=Ex_BSGS(y,z,p);
(x==-1)?printf("Orz, I cannot find x!\n"):printf("%lld\n",x);
}
}
return 0;
}
