yukicoder 251 大きな桁の復習問題(1)
問題
方針
$m=129402307$ とおく. まず $N$ を $N%m$ に置き換える. $N \neq 0$ のときはフェルマーの小定理より $N^M = N^{M%(m-1)}$ を求める. $N = 0$ のときは注意が必要.もとの式に戻ると,$M=0$ なら $1$, そうでなければ $0$ となる.
実装
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll modstr(const string &s, ll m){
ll a = 0;
for(auto c:s) a = (c-'0'+a*10) % m;
return a;
}
ll modpow(ll x, ll y, ll m){
if(y==0) return 1;
ll res = modpow(x,y/2,m);
return res * res % m * (y&1 ? x : 1) % m;
}
ll modpow(const string &s, const string &t, ll m){
assert(s != "0" || t != "0");
ll N = modstr(s,m);
return N==0 ? (t=="0"?1:0) : modpow(N,modstr(t,m-1),m);
}
int main(){
string s,t;
cin >> s >> t;
cout << modpow(s,t,129402307) << endl;
}
$N$ が割り切れる場合を忘れて WA りまくったのでライブラリ化.