| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 6195 | Accepted: 1500 |
Description
Little Y finds there is a very interesting formula in mathematics:
XY mod Z = K
Given X, Y, Z, we all know how to figure outK fast. However, given X, Z, K, could you figure outY fast?
Input
Output
Sample Input
5 58 33 2 4 3 0 0 0
Sample Output
9 No Solution
模板题，测试模板
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/2 21:01:29
File Name :7.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
class HASH{
public:
struct node{
ll next,first,second;
}edge[140000];
ll tol,head[140100];
void clear(){
memset(head,-1,sizeof(head));
tol=0;
}
void add(ll x,ll y){
if(find(x)!=-1)return;
ll t=x%65535;
edge[tol].next=head[t];
edge[tol].first=x;
edge[tol].second=y;
head[t]=tol++;
}
ll find(ll x){
ll t=x%65535;
for(ll i=head[t];i!=-1;i=edge[i].next)
if(edge[i].first==x)return edge[i].second;
return -1;
}
}mi;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){d=a;x=1;y=0;return;}
exgcd(b,a%b,d,y,x);y-=x*(a/b);
}
ll pow_mod(ll a,ll n,ll m){
ll res=1;
a%=m;
while(n){
if(n&1) res=res*a%m;
a=a*a%m;
n>>=1;
}
return res;
}
ll BabyStep_GiantStep(ll A,ll B,ll C){
B%=C;
ll tmp=1;mi.clear();
for(int i=0;i<=100;++i){
if(tmp==B%C) return i;
tmp=tmp*A%C;
}
ll D=1,d=0;
while((tmp=gcd(A,C))!=1){
if(B%tmp) return -1;
C/=tmp;
B/=tmp;
D=D*A/tmp%C;
d++;
}
ll m=(ll)ceil(sqrt((double)C));
tmp=1;
for(int i=0;i<=m;++i){
mi.add(tmp,i);
tmp=tmp*A%C;
}
ll x,y,K=pow_mod(A,m,C),dd;
for(int i=0;i<=m;++i)
{
exgcd(D,C,dd,x,y);
tmp=((B*x)%C+C)%C;
if((y=mi.find(tmp))!=-1)return i*m+y+d;
D=D*K%C;
}
return -1;
}
int main(){
ll A,B,C;
while(cin>>A>>C>>B){
if(!A&&!B&&!C) break;
ll ans=BabyStep_GiantStep(A,B,C);
if(ans==-1)cout<<"No Solution"<<endl;
else cout<<ans<<endl;
}
return 0;
}
POJ 3243 大步小步算法,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22828659