文件详细信息

下载本文件

本文件的大小为 1316 字节。

#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]);
}
uint p,a,b,m,num,step;
void solve(){
	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()){
			write(i*m-map[num]),putchar('\n');
			return;
		}
	}
	puts("no solution");
}
int main(){
	while(read(p),read(a),read(b),p)solve();
	return 0;
}