結果

問題 No.981 一般冪乗根
ユーザー 👑 testestest
提出日時 2020-02-14 15:11:28
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 123 ms / 6,000 ms
コード長 3,755 bytes
コンパイル時間 311 ms
コンパイル使用メモリ 34,936 KB
実行使用メモリ 9,264 KB
最終ジャッジ日時 2024-10-10 00:03:45
合計ジャッジ時間 73,769 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define ll long long
#define ull unsigned long long

ll mulmod(ll a,ll n,ll m){
	ull x=0;
	a%=m,n%=m;
	while(n){
		if(n%2)x=(x+a)%m;
		a=(a+a)%m;
		n/=2;
	}
	return (ll)x;
}

ll powmod(ll a,ll n,ll m){
	ll x=1;
	a%=m;
	while(n){
		if(n%2)x=mulmod(x,a,m);
		a=mulmod(a,a,m);
		n/=2;
	}
	return x;
}

ll gcd(ll x,ll y){
	while(y){
		ll t=x%y;
		x=y;
		y=t;
	}
	return x;
}

ll inv(ll a,ll p){
	ll b=p,tx,ty,t,x=1,y=0,x2=0,y2=1;
	while(b){
		tx=x-a/b*x2;x=x2;x2=tx;
		ty=y-a/b*y2;y=y2;y2=ty;
		t=a%b;a=b;b=t;
	}
	if(a!=1)return-1;
	return x>0?x:x+p;
}

ll intsqrt(ll n){
	ll x=sqrt(n);
	while((x+1)*(x+1)<=n)x++;
	return x;
}
ll intcbrt(ll n){
	ll x=cbrt(n);
	while((x+1)*(x+1)*(x+1)<=n)x++;
	return x;
}

typedef struct pair{ll a;int n;}P;
int Pcmp(const void*p,const void*q){
	if((*(P*)p).a<(*(P*)q).a)return -1;
	return 1;
}
P memo[100000];
int memosize;
void subsubpre(ll g,ll p,ll mod){
	//(Z/modZ)^*における位数pの元gに対し
	//g^-nを0<=n<=sqrt(p)くらいの範囲でメモ
	g=inv(g,mod);
	memosize=sqrt(p)+10;
	ll x=1;
	for(int i=0;i<memosize;i++){
		memo[i].a=x;
		memo[i].n=i;
		x=mulmod(x,g,mod);
	}
	qsort(memo,memosize,sizeof(P),Pcmp);
}

int subsub(ll g,ll x,ll p,ll mod){
	//(Z/modZ)^*における位数pの元g,xに対し、x=g^-nを満たすnの1つを返す
	ll gM=powmod(g,memosize,mod);
	for(int i=0;;i++){
		int l=0,r=memosize;
		while(r-l>1){
			int m=(l+r)/2;
			if(memo[m].a<=x)l=m;
			else r=m;
		}
		if(memo[l].a==x)return i*memosize+memo[l].n;
		x=mulmod(x,gM,mod);
	}
	
}

ll modrootsub(ll a,ll p,ll e,ll mod){
	// 0 < e < ord_p(mod-1)
	ll q=mod-1;
	int s=0;
	while(q%p==0)q/=p,s++;
	// Z/(p^s)Z * Z/qZ
	
	ll pe=1;
	for(int i=0;i<e;i++)pe*=p;
//	ll d=crt(pe-1,pe,0,q);
	ll d=inv(pe-q%pe,pe)*q;
	
	// (p^e)ans = a + err
	ll ans=powmod(a,(d+1)/pe,mod);
	ll err=powmod(a, d      ,mod);
	if(err==1)return ans;
	int temp=1;
	while(powmod(++temp,(mod-1)/p,mod)==1);
	ll z=powmod(temp,q,mod);
	ll g=powmod(temp,(mod-1)/p,mod);
	
	subsubpre(g,p,mod);
	
	while(err!=1){
		//上から非0の桁数を求める
		ll t=err,pre,cnt=0;
		while(t!=1){
			pre=t;
			t=powmod(t,p,mod);
			cnt++;
		}
		int n=subsub(g,pre,p,mod);
		//所定の桁を良しなにする
		//ansにz^(p^(s-cnt-e)*n)
		//errにz^(p^(s-cnt  )*n)
		t=powmod(z,n,mod);
		for(int i=0;i<s-cnt-e;i++)t=powmod(t,p,mod);
		ans=mulmod(ans,t,mod);
		for(int i=0;i<e;i++)t=powmod(t,p,mod);
		err=mulmod(err,t,mod);
	}
	return ans;
}

ll modrootsub2(ll a,ll n,ll p){
	//Assume:
	//for all prime q. 0<ord_q(n)⇒ord_q(p-1)<=ord_q(n)
	
	ll p1=p-1,p2=1;
	ll temp;
	while(temp=gcd(p1,n),temp!=1){
		p1/=temp;
		p2*=temp;
	}
	
	ll d=inv(n%p1,p1);
	return powmod(a,d,p);
}

ll modroot(ll a,ll n,ll p){
	//Assume: p is prime
	//x^n=a mod pとなるxの1つを返す
	ll d=gcd(p-1,n);
	if(powmod(a,(p-1)/d,p)!=1)return -1;
	a=powmod(a,inv(n/d,(p-1)/d),p);
	n=d;
	// n | p-1
	
	//0<ord_q(n)<ord_q(p-1)なる素数qを分離する
	ll d1=n,d2=1;
	ll temp;
	while(temp=gcd((p-1)/n,d1),temp!=1){
		d1/=temp;
		d2*=temp;
	}
	
	//d1はまとめてえいや
	a=modrootsub2(a,d1,p);
	//d2は因数分解してはい
	//d2の因数であるようなqについて、ord_q(p-1)>=2なので
	//そのようなqであってp^(1/4)より大きなものは高々1つ
	for(ll i=2;i*i*i*i<=p-1;i++)if(d2%i==0){
		d2/=i;
		int e=1;
		while(d2%i==0)d2/=i,e++;
		a=modrootsub(a,i,e,p);
	}
	
	if(d2!=1){
		//d2はp^(1/4)より大きな素数qか、その平方
		//(ord_q(d2)<ord_q(p-1)<4なので)
		ll q2=intsqrt(d2);
		if(q2*q2==d2)a=modrootsub(a,q2,2,p);
		else a=modrootsub(a,d2,1,p);
	}
	
	return a;
}


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		ll a,n,m;
		scanf("%lld%lld%lld",&m,&n,&a);
		printf("%lld\n",modroot(a,n,m));
	}
}
0