BZOJ1467_Pku3243 clever Y_EXBSGS

Description

小Y发现，数学中有一个很有趣的式子： X^Y mod Z = K 给出X、Y、Z，我们都知道如何很快的计算K。但是如果给出X、Z、K，你是否知道如何快速的计算Y呢？

Input

本题由多组数据（不超过20组），每组测试数据包含一行三个整数X、Z、K（0 <= X, Z, K <= 109）。输入文件一行由三个空格隔开的0结尾。

Output

对于每组数据：如果无解则输出一行No Solution，否则输出一行一个整数Y(0 <= Y < Z)，使得其满足XY mod Z = K，如果有多个解输出最小的一个Y。

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

exbsgs模板题，用来处理模数非质数的情况。

具体实现比较简单，注意前num个数需要枚举。

挖坑待填...

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <map>

#include <math.h>

using namespace std;

typedef long long ll;

map<ll,int>mp;

void exgcd(ll a,ll b,ll &x,ll &y,ll &p) {

    if(!b) {x=1; y=0; p=a; return ;}

    exgcd(b,a%b,y,x,p);

    y-=a/b*x;

}

ll gcd(ll x,ll y) {

    return y?gcd(y,x%y):x;

}

ll EXBSGS(ll a,ll b,ll n) {

    if(n==1) return b==0?0:-1;

    if(a%n==0) return b==0?0:1;

    mp.clear();

    ll r,D=1,num=0,now,base=1;

    while((r=gcd(a,n))>1) {

        if(b%r) return -1;

        num++; b/=r; n/=r; D=D*a/r%n;

    }

    int i;

    for(i=0,now=1;i<num;i++,now=now*a%n)

        if(now==b) return i;

    ll m=ceil(sqrt(n));

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

        if(!mp.count(base)) mp[base]=i;

        base=base*a%n;

    }

    ll x,y,p;

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

        exgcd(D,n,x,y,p);

        x=(x*b%n+n)%n;

        if(mp.count(x)) return i*m+mp[x]+num;

        D=D*base%n;

    }

    return -1;

}

int main() {

    ll a,b,n;

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

        if(a==0&&b==0&&n==0) return 0;

        ll ans=EXBSGS(a,b,n);

        if(ans==-1) puts("No Solution");

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

    }

}

秒客网