Clever Y
Time Limit:5000MSMemory Limit:65536K
Total Submissions:6861Accepted:1676
Description
Little Y finds there is a very interesting formula in mathematics:
XYmod Z = K
GivenX,Y,Z, we all know how to figure outKfast. However, givenX,Z,K, could you figure outYfast?
Input
Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integersX,Z,K(0 ≤X,Z,K≤ 109).Input file ends with 3 zeros separated by spaces.
Output
For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasibleY(0 ≤Y<Z). Otherwise output the minimumYyou find.
Sample Input
5 58 332 4 30 0 0
Sample Output
9No Solution
Source
, Guo, Huayang
/* ***********************************************Author:CKbossCreated Time :2015年03月31日 星期二 20时02分38秒File Name:POJ3243.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long int LL;const int MOD=76543;int hs[MOD],head[MOD],next[MOD],id[MOD],top;void insert(int x,int y){int k=x%MOD;hs[top]=x; id[top]=y;next[top]=head[k]; head[k]=top++;}int find(int x){int k=x%MOD;for(int i=head[k];~i;i=next[i])if(hs[i]==x) return id[i];return -1;}int BSGS(int a,int b,int n){memset(head,-1,sizeof(head));top=1;if(b==1) return 0;int m=sqrt(n*1.0),j;LL x=1,p=1;for(int i=0;i<m;i++,p=p*a%n) insert(p*b%n,i);for(LL i=m;;i+=m){if((j=find(x=x*p%n))!=-1) return i-j;if(i>n) break;}return -1;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int a,b,n;while(scanf("%d%d%d",&a,&n,&b)!=EOF){if(a==0&&b==0&&n==0) break;int ans=BSGS(a,b,n);if(ans==-1) puts("No Solution");else printf("%d\n",ans);}return 0;}
，通电话，旅行，重复一个承诺和梦想，
