結果

問題 No.981 一般冪乗根
ユーザー 👑 testestest
提出日時 2020-02-10 15:19:52
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 6,000 ms
コード長 1,929 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 32,368 KB
実行使用メモリ 8,480 KB
最終ジャッジ日時 2024-10-09 21:46:11
合計ジャッジ時間 83,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30 WA * 8 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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;
}

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;
}

int modrootsub(int a,int p,int e,int mod){
	int q=mod-1;
	int s=0;
	while(q%p==0)q/=p,s++;
	// Z/(p^s)Z * Z/qZ
	
	
	int 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;
		for(int i=0;i<e;i++)t=powmod(t,p,mod);
		err=err*t%mod;
	}
	return ans;
}

int modroot(int a,int n,int p){
	//p は素数
	//x^n=a mod pとなるxの1つを返す
	int 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;
	for(int i=2;i*i<=n;i++)if(n%i==0){
		n/=i;
		int e=1;
		while(n%i==0)n/=i,e++;
		a=modrootsub(a,i,e,p);
	}
	if(n>1)a=modrootsub(a,n,1,p);
	return a;
}

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