結果

問題 No.981 一般冪乗根
ユーザー 👑 testestest
提出日時 2020-02-14 14:08:12
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 6,000 ms
コード長 3,089 bytes
コンパイル時間 739 ms
コンパイル使用メモリ 34,668 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-09 23:50:03
合計ジャッジ時間 40,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<math.h>
#include<time.h>
#define ll long long

//ll未対応
ll powmod(ll a,ll n,int m){
	ll x=1;
	a%=m;
	while(n){
		if(n%2)x=x*a%m;
		a=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;
}

int subsub(ll x,ll y,int p,int mod){
	//(Z/modZ)^*における位数pの元x,yに対し、x^n*y=1を満たすnを返す
	int cnt=0;
	while(y!=1){
		y=y*x%mod;
		cnt++;
	}
	return cnt;
}

ll modrootsub(ll a,ll p,ll e,ll mod){
	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;
//	int 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);
	int z=powmod(temp,q,mod);
	int g=powmod(temp,(mod-1)/p,mod);
	
	while(err!=1){
		//上から非0の桁数を求める
		int 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=ans*t%mod;//<--modがでかいとoverflow
		for(int i=0;i<e;i++)t=powmod(t,p,mod);
		err=err*t%mod;//<--modがでかいとoverflow
	}
	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%n,n)*p1;//<--64bitに収まらない
	//return powmod(a,(d+1)/n,p);
	ll d=inv(n%p1,p1);
	return powmod(a,d,p);
}

ll modroot(ll a,ll n,ll p){
	//p は素数
	//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のperfect power
		ll q2=intsqrt(d2);
		ll q3=intcbrt(d2);
		if(q2*q2==d2)a=modrootsub(a,q2,2,p);
		else if(q3*q3*q3==d2)a=modrootsub(a,q3,3,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