程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 3243 Clever Y BSGS

POJ 3243 Clever Y BSGS

編輯：關於C++

Clever Y Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 6861 Accepted: 1676

Description

Little Y finds there is a very interesting formula in mathematics:

X^Y mod Z = K

Given X, Y, Z, we all know how to figure out K fast. However, given X, Z, K, could you figure out Y fast?

Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integers X, Z, K (0 ≤ X, Z, K ≤ 10⁹).
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 feasible Y (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution

Source

POJ Monthly--2007.07.08, Guo, Huayang

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月31日 星期二 20時02分38秒
File Name     :POJ3243.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

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;in) 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;
}