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