文件详细信息

下载本文件

本文件的大小为 2045 字节。

#include<chrono>
#include<cmath>
#include<cstdio>
#include<ext/pb_ds/assoc_container.hpp>
typedef unsigned int uint;
typedef unsigned long long ull;
struct custom_hash{
	static ull splitmix64(ull x){
		x+=0x9e3779b97f4a7c15;
		x=(x^(x>>30))*0xbf58476d1ce4e5b9;
		x=(x^(x>>27))*0x94d049bb133111eb;
		return x^(x>>31);
	}
	size_t operator()(ull x)const{
		static const ull FIXED_RANDOM=std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x+FIXED_RANDOM);
	}
};
__gnu_pbds::gp_hash_table<uint,uint,custom_hash>map;
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57){
		if(ch==EOF)return;
		ch=getchar();
	}
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
template<typename T>
T gcd(const T a,const T b){
	return b?gcd(b,a%b):a;
}
ull qpow(ull a,uint x,const ull P){
	ull ans=1;
	while(x){
		if(x&1)ans=ans*a%P;
		a=a*a%P;
		x>>=1;
	}
	return ans;
}
void exgcd(int a,int b,int&x,int&y){
	if(!b)x=1,y=0;
	else{
		exgcd(b,a%b,y,x);
		y-=a/b*x;
	}
}
uint inv(const int a,const int b){
	static int x,y;
	exgcd(a,b,x,y);
	return(x%b+b)%b;
}
uint p,a,b;
int ans;
int bsgs(uint p,uint a,uint b){
	static uint m,num,step;
	m=uint(sqrt(p))+1;
	map.clear();
	num=b;
	for(uint i=0;i<=m;i++){
		map[num]=i;
		num=(ull)num*a%p;
	}
	num=step=1;
	for(uint i=1;i<=m;i++)step=(ull)step*a%p;
	for(uint i=1;i<=m+1;i++){
		num=(ull)num*step%p;
		if(map.find(num)!=map.end())return i*m-map[num];
	}
	return-1;
}
int exbsgs(uint p,uint a,uint b){
	a%=p,b%=p;
	if(b==1)return 0;
	uint g,d=1,k=0;
	while((g=gcd(a,p))!=1){
		if(b%g)return-1;
		k++;
		b/=g;
		p/=g;
		d=(ull)d*(a/g)%p;
		if(b==d)return k;
	}
	int ans=bsgs(p,a,(ull)b*inv(d,p)%p);
	if(ans==-1)return-1;
	return ans+k;
}
int main(){
	while(read(a),read(p),read(b),p){
		ans=exbsgs(p,a,b);
		if(ans==-1)puts("No Solution");
		else write(ans),putchar('\n');
	}
	return 0;
}