牛客20347 SDOI2011计算器（bsgs

https://ac.nowcoder.com/acm/problem/20347

这篇是为了补bsgs（北上广深算法）。

题意：

1、给定y,z,p,计算Y^Z Mod P 的值；

2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；

3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

思路：

1.当然是裸的快速幂取模啦。

2.原式<=>yx+pk=z有解，exgcd记录d=gcd(y,p)，看是否d|z即可。

3.要求满足形如a^x ≡ b (mod p)的最小非负整数x。

由周期性只需在[0,p)讨论即可，证明的话，抽屉原理显然，或者由费马小定理（当p为质数且(a,p)=1时 a^(p-1)=1 (mod p) )能推出a^k=a^(k mod (p-1)) (mod p)。

把x分块，每块长度是m，其中m=ceil(sqrt(p))，则a^(i*m-j) = b (mod p)，移项得a^(i*m) = b*a^j (mod p)

枚举j（范围0-m)，将b*a^j存入哈希表。

枚举i（范围1-m），从哈希表找出第一个满足a^(i*m) = b*a^j (mod p)的i

此时x = i*m-j就是答案

时间复杂度O(m+p/m),m取√p时最优。

 #include<bits/stdc++.h>

 using namespace std;

 #define int long long

 int T,k,a,b,p;

 map<int,int>mp;

 int kuai(int a,int b,int mod)

 {

     if(b==)return a;

     int x=kuai(a,b/,mod);

     if(b%==)return x*x%mod;

     else return x*x%mod*a%mod;

 }

 void exgcd(int a,int b,int &d,int &x,int &y)

 {

     if(b==){d=a;x=;y=;}

     else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}

 }

 int bsgs(int a,int b,int p){

     a%=p;b%=p;

     if(!a&&!b) return ;

     if(!a||!b) return -;

     mp.clear();

     int m = ceil(sqrt(1.0*p)),tmp=;

     mp[tmp*b%p]=;

     for(int j=;j<=m;j++){

         tmp = tmp*a%p;

         if(!mp[tmp*b%p]) mp[tmp*b%p] = j;

     }

     int t = ,ans;

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

         t=t*tmp%p;

         if(mp[t]){

             ans = i*m-mp[t];

             return (ans%p+p)%p;

         }

     }

     return -;

 }

 signed main(){

    scanf("%lld%lld",&T,&k);

     while(T--)

     {

         scanf("%lld%lld%lld",&a,&b,&p);

         if(k==)printf("%lld\n",kuai(a,b,p)%p);

         else if(k==)

         {

             int x=,y=,d;

             exgcd(a,p,d,x,y);

             if(b%d)

             {

                 puts("Orz, I cannot find x!");

                 continue;

             }

             x=x*b/d;

             x=(x%p+p)%p;

             printf("%lld\n",x);

         }

         else{

             int ans=bsgs(a,b,p);

             if(ans==-)puts("Orz, I cannot find x!");

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

         }

     }

     return ;

 }

巴特西

牛客20347 SDOI2011计算器（bsgs

最新文章

热门文章