【POJ2417】baby step giant step

时间：2021-10-11 06:31:20

　　最近在学习数论，然而发现之前学的baby step giant step又忘了，于是去翻了翻以前的代码，又复习了一下。

　　觉得总是忘记是因为没有彻底理解啊。

　　

【POJ2417】baby step giant step

　　注意baby step giant step只能用在b和p互质的情况下，因为只有b和p互质的情况下，b才有mod p下的逆元。（下面要用到逆元）

　　当b和p不互质，就要处理一下。现在就正在做这么一题，方法以后再写。

　　【POJ2417】baby step giant step

　　求a^(-m)就用到了求逆元了，那么如何求逆元呢？我学了两种方法：

　　·1：欧拉定理：当a和n互质，a^φ ( n) ≡ 1(mod n)。【φ ( n) 是小于等于n的与n互质的数的个数】

　　·2：拓展欧几里德：设a在mod n下的逆元是x，则满足：ax ≡ 1(mod n)

           即ax+ny=1。（a和n是常数，x和y是未知数，用拓展欧几里德求解即可）

　　注：只有当a和n互质，a才有mod n下的逆元。

　　代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define LL long long

 #define Maxn 1000010

 struct node

 {

     int idx;

     LL val;

 }baby[Maxn];

 bool cmp(node x,node y) {return x.val!=y.val ? x.val<y.val : x.idx<y.idx;}

 int binsearch(int cnt,LL tmp)

 {

     int head=,tail=cnt;

     while(head<=tail)

     {

         int mid=(head+tail)>>;

         if(baby[mid].val==tmp) return baby[mid].idx;

         if(baby[mid].val<tmp) head=mid+;

         else tail=mid-;

     }

     return -;

 }

 LL powmod(LL a,LL b,LL mod)

 {

     LL ret=;

     a%=mod;

     while(b)

     {

         if(b&) ret=(ret*a)%mod;

         a=(a*a)%mod;

         b>>=;

     }

     return ret;

 }

 int main()

 {

     LL p,b,n;

     while(scanf("%lld%lld%lld",&p,&b,&n)!=EOF)

     {

         int m=(int)ceil(sqrt((double)(p-))),cnt=;

         baby[].idx=,baby[].val=;

         for(int i=;i<m;i++)

          baby[i].idx=i,baby[i].val=(baby[i-].val*b)%p;

         sort(baby,baby+m,cmp);

         for(int i=;i<m;i++)

           if(baby[i].val!=baby[cnt].val) baby[++cnt]=baby[i];

         LL bm=powmod(powmod(b,p-,p),m,p);

         //printf("bm = %lld\n",bm);

         int ans=-;

         LL tmp=n;

         for(int i=;i<m;i++)

         {

             int pos=binsearch(cnt,tmp);

             if(pos!=-)

             {

                 ans=i*m+pos;

                 break;

             }

             tmp=(tmp*bm)%p;

         }

         if(ans==-) printf("no solution\n");

         else printf("%d\n",ans);

     }

     return ;

 }

poj2417

2016-02-03 09:50:33

 

相关文章