kmjp's blog

競技プログラミング参加記です

yukicoder : No.1287 えぬけー

今回★の割にちょっと難しかったかも…と思った回。
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乗根を求めるのにもっと複雑なコードを使ってたけど、こっちの方が単純だな。