一般形式

求解同余方程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;
}