1007.cpp

来自「HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告」· C++ 代码 · 共 193 行

#include<iostream>
#include<cmath>
#include<time.h>
using namespace std;
typedef long long llong;
#define SIZE 65536
struct Hash{int next;llong modres,pval;}hash[SIZE<<2];
int top;
llong P,B,N,tb,ad;
bool flag[SIZE];
void init(){memset(flag,false,sizeof(flag));top=SIZE;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void ins(int pval,int modres)
{
	int key=modres&(SIZE-1);
	if(!flag[key]){flag[key]=true;
	hash[key].next=-1;
	hash[key].modres=modres;
	hash[key].pval=pval;
	return;
	}
	while(key!=-1)
	{
		if(hash[key].next==-1)break;
		if(hash[key].modres==modres)
		{
			return;
		}
		key=hash[key].next;
	}
	hash[key].next=++top;
	hash[top].next=-1;
	hash[top].pval=pval;
	hash[top].modres=modres;
}
int PVAL(int modres)
{
	int key=modres&(SIZE-1);
	if(!flag[key])return -1;
	while(key!=-1)
	{
		if(hash[key].modres==modres)return hash[key].pval;
		key=hash[key].next;
	}
	return -1;
}
llong mod(llong a,llong b,llong c)
{
	llong ret=1;
	while(b)
	{
		if(b&0x1)
		{
			ret*=a;
			if(ret>=c)ret%=c;
		}
		a*=a;
		if(a>=c)a%=c;
		b>>=1;
	}
	return ret;
}
llong ext_gcd(llong a,llong b,llong& x,llong & y){
	llong t,ret;
	if (!b){
		x=1,y=0;
		return a;
	}
	ret=ext_gcd(b,a%b,x,y);
	t=x,x=y,y=t-a/b*y;
	return ret;
}
llong modular_linear(llong a,llong b,llong n,llong *sol){
	llong ret,d,e,x,y,i;
	d=ext_gcd(a,n,x,y);
	if (b%d)
		return 0;
	e=(x*(b/d)%n+n)%n;
	for (i=0;i<d;i++)
		sol[i]=(e+i*(n/d))%n;
	return d;
}
llong s[1000001];
llong solve()
{
	llong m=ceil(sqrt((double)P));
	llong i,j,tt=1;
	init();
	for(i=0;i<=m;++i)
         {
           tt%=P;
           ins(i,tt);
           tt*=B;
         }
	llong buf=mod(B,m,P);
	llong Y=tb%P,TY;
	llong fnd,tmp=-1,ans=-1;
	for(i=0;i<=m;++i)
	{
		if(ans!=-1&&i*m>=ans)break;
		TY=modular_linear(Y,N,P,s);
		tt=0x7fffffff;
		for(j=0;j<TY;++j){
			fnd=PVAL(s[j]);
			if(fnd+1)
			{
				tt=min(fnd,tt);
			}
		}
		if(tt!=0x7fffffff)
			return i*m+tt;
		Y*=buf;
		Y%=P;
	}
	return -1;
}
llong solve1()
{
	llong m=ceil(sqrt((double)P));
	llong i,j,tt=1;
	init();
	for(i=0;i<=m;++i)
         {
           tt%=P;
           ins(i,tt);
           tt*=B;
         }
	llong buf=mod(B,m,P);
	llong Y=tb%P,TY;
	llong fnd,tmp=-1,ans=-1;
	for(i=0;i<=m;++i)
	{
		if(ans!=-1&&i*m>=ans)break;
		TY=modular_linear(Y,N,P,s);
		tt=0x7fffffff;
		for(j=0;j<TY;++j){
			fnd=PVAL(s[j]);
			if(fnd+1)
			{
				tt=min(fnd,tt);
			}
		}
		if(tt!=0x7fffffff)
			return i*m+tt;
		Y*=buf;
		Y%=P;
	}
	return -1;
}
int readint()
{
	int ret=0;
	char c;
	if((c=getchar())==EOF)return -1;
	ungetc(c,stdin);
	while((c=getchar())<'0'||c>'9');
	ret=(c-'0');
	while((c=getchar())>='0'&&c<='9')ret=ret*10+(c-'0');
	return ret;
}
int main()
{
	llong ans;
	//clock_t A=clock();
	//OPEN
	//freopen("D:\\out.txt","w",stdout);
	while(1)
	{
		B=readint();
		if(B==-1)break;
		P=readint();
		N=readint();
		if(N>=P){puts("Orz,I can’t find D!");continue;}
		ad=0;
		llong orz=gcd(N,gcd(B,P));
		if(orz!=1)
		{
			P/=orz;
			N/=orz;
			tb=B/orz;
			ad=1;
		}
		else
			tb=1,ad=0;
		ans=solve();
		if(ans==-1)
			puts("Orz,I can’t find D!");
		else
			printf("%lld\n",ans+ad);
	}
	//cout<<"times : "<<clock()-A<<endl;
	return 0;
}