【SDOI2011】【BZOJ2242】计算器

Description

你被要求设计一个计算器完成以下三项任务：
　　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)的最小非负整数 。

Solution

一道裸的数论题。
∙第一项任务，很简单快速幂。
∙第二项任务，运用exgcd：首先式子可以转变成：
xy=np+z
xy−np=z
明显的exgcd形式
设t=gcd(y,p)，如果z是t的倍数才有解，原因百科上有讲。
然后y,p,z分别除以t，这样y就与p互质了，那么新的y,p上gcd(y,p)=1，所以可以用exgcd来解决xy−np=gcd(y,p)=1这个情况。
但是后面是等于1不是等于z，怎么办。
直接用解出来的x乘上z就可以了，因为
xy−np=1
后面乘上z
xyz−npz=z
所以y∗(xz)−p∗(n∗z)=z
那么答案自然就是xz了。然而要输出最小非负整数。
那么就一直用xz+p，直到得出的ans>=0为止。
因为y∗(xz+p)−p∗(n∗z+y)=z
拆开括号：
xyz+yp−npz−yp=z
yp正负抵消。
所以，一般ax+by=z得出的一种解，要得出其他的解让x不断+b，y不断-a就可以了。
∙第三项任务：BSGS裸题，参考​​BSGS算法学习小记​​

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm> 
#include<map>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;
ll i,j,k,l,t,n,m,ans,x,y,p;
map<int,int>a;
ll qsm(ll x,ll y){
    ll z=1;
    for(;y;y/=2,x=x*x%p)if(y&1)z=z*x%p;
    return z;
}
ll gcd(ll x,ll y){return (!y)?x:gcd(y,x%y);}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}
void cheng(ll y,ll z){
    p=-p;    
    ll t=gcd(y,p);
    if(z%t){printf("Orz, I cannot find x!\n");return;}
    y/=t,p/=t,z/=t;
    ll a,b;exgcd(y,p,a,b);
    a=a*z%p;
    while(a<0)a+=p;
    printf("%d\n",a);
} 
void BSGS(ll x,ll z){
    ll i,j,k=1,y=z%p;x%=p;
    if(!x&&!z){printf("1\n");return;}
    if(!x){printf("Orz, I cannot find x!\n");return;}
    ll m=ceil(sqrt(p-1));
    ll ni=qsm(x,m);ni=qsm(ni,p-2);
    a.clear();
    a[1]=m+1;
    fo(j,1,m-1){
        k=k*x%p;
        if(!a[k])a[k]=j;
    }    
    fo(i,0,m-1){
        ll u=a[y];
        if(u){
            if(u==m+1)printf("%lld\n",i*m);
            else printf("%lld\n",i*m+u);
            return;
        }
        y=y*ni%p;    
    }
    printf("Orz, I cannot find x!\n");
} 
int main(){
    scanf("%lld%lld",&n,&m);
    fo(i,1,n){
        scanf("%lld%lld%lld",&x,&y,&p);
        if(m==1)printf("%lld\n",qsm(x,y));
        else if(m==2)cheng(x,y);
        else BSGS(x,y);
    }
}