今回★の割にちょっと難しかったかも…と思った回。
https://yukicoder.me/problems/no/1287
問題
整数X,Kが与えられる。
XのK乗根、すなわちX=N^K (mod 10^9+7)となるNを求めよ。
解法
p=10^9+6として、bK=a(p-1)+1となるa,bが取れれば
X^b=(N^bK)=N^(a(p-1)+1)=N (mod 10^9+7)
となる。
a,bは拡張ユークリッドの互除法で解いてもよいし、bK=1 (mod (p-1))なbを求めればよいのでb=K^(φ(p-1)-1)で求めてもよい。
int T; const ll mo=1000000007; ll modpow(ll a, ll n = mo-2,ll mo=mo) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { int X,K; cin>>X>>K; if(X==0) { cout<<0<<endl; } else { ll b=modpow(K,500000001,mo-1); cout<<modpow(X,b)<<endl; } } }
まとめ
昔N乗根を求めるのにもっと複雑なコードを使ってたけど、こっちの方が単純だな。