Codeforces 17 D. Notepad
問題
n桁のb進数の数のうち、leading zeroがないものを全てノートに書く。
1ページあたりc個の数字を書くものとするとき、最後のページに書かれる文字の数はいくつか求めよ。
制約条件
b≦10^(10^6)
n≦10^(10^6)
c≦10^9
方針
求める数は(b-1)*b^(n-1)%cである。
b^n乗(nは非常に大きい)を高速に求められればよい。
nが10進数でa0+a1*10+a2*10^2+…+ak*10^kと書けるとすると、
a^n = (…((a^ak)^10^ak-1)^10…)^a0となる。
すなわち、頭の位から順にai乗にして、10乗にしてという操作を繰り返せばa^nが求まることになる。
実際にはこれを剰余を取りながら行う。
オイラーのphi関数を利用して、ある程度大きいkに対して
a^(phi(c)+k) ≡ a^k (mod c)が成り立つことを利用する別解も存在する。
ソースコード
string B,N; int c; inline ll modpow(ll p,int n,int mod){ ll res=1; for(;n;n>>=1){ if(n&1)res=res*p%mod; p=p*p%mod; } return res; } void run() { cin>>B>>N>>c; for(int i=N.size()-1;i>=0;i--){ if(N[i]=='0')N[i]='9'; else{ N[i]--; break; } } ll b=0,p=1; rep(i,B.size())b=(b*10+B[i]-'0')%c; rep(i,N.size())p=modpow(p,10,c)*modpow(b,N[i]-'0',c)%c; p=p*(b+c-1)%c; cout<<(p?p:c)<<endl; }