BSGS

桑树下的邂逅 · 2019-02-22 21:38:36 · 个人记录

求解 x^{k}=y(mod p) $

令 m=\sqrt{p}

#include<cstdio>
#include<cmath>
#include<unordered_map>
using namespace std;
unordered_map<int,int>a;
int p,x,y;
int fpow(int x,int y){
    int ans=1;
    while(y){
        if(y%2) ans=1ll*ans*x%p;
        x=1ll*x*x%p;y>>=1; 
    }
    return ans;
}
int main(){
    scanf("%d%d%d",&p,&x,&y);
    int m=sqrt(p)+1,s=y;
    for(int i=0;i<m;i++){
        a[s]=i;
        s=1ll*s*x%p;
    }
    int temp=fpow(x,m);s=1;
    for(int i=1;i<=m;i++){
        s=1ll*s*temp%p;
        if(a.count(s)){
            printf("%d\n",i*m-a[s]);
            return 0;
        } 
    }
    printf("no solution");
    return 0;
}