yukicoder No.16 累乗の加算

繰り返し2乗法
普通a^mを計算しようと思ったら、aをm回掛け算しないといけないが
mを2進数展開していい感じに工夫するとO(log2(m))くらいで計算できるというやつ

――――
a^(2^n)はnが小さい方から計算することで、n回の掛け算で計算できる
a*a=a^2
(a^2)*(a^2)=a^(2^2)
(a^(2^2))*(a^(2^2))=a^(2^3)
…
mの2進数展開によりm=Σ(2^n)の形でかけるので
a^m=Πa^(2^n)として、mのbitpop数回の掛け算で計算できる
例えば19=10011(2)なので
a^19=a^16*a^2*a^1
――――

と理解していたので、

int pow(int a,int m){
	int x=1;t=a;
	for(i=0;i<32;i++){
		if(m&1<<i)x*=m;
		t*=t;
		//1の位があるならa^1を掛ける
		//2の位があるならa^2を掛ける
		//4の位があるならa^4を掛ける
		//…
	}
	return x;
}

と実装するのが自然だと思っていたのだけど、再帰で計算させるのが普通らしい

int pow(int a,int m){
	if(m==0)return 1;
	if(m%2==0)return pow(a*a,m/2);
	return pow(a*a,m/2)*a;
}

こっちは要するに「a^2nって(a^2)^nと等価じゃん」という発想

ということで以上をまとめて冒頭の問題の答え

int q=1000003;
int p(int a,int m){
	if(m==0)return 1;
	if(m%2==0)return p(1L*a*a%q,m/2);
	return p(1L*a*a%q,m/2)*1L*a%q;
}
int main(){
	int a,n,i,t,s=0;
	scanf("%d%d",&a,&n);
	for(i=0;i<n;i++){
		scanf("%d",&t);
		s+=p(a,t);
		//q以下のものをn回足すだけなのでオーバーフローしない
	}
	printf("%d",s%q);
	return 0;
}

累乗の計算をまとめる

int main(){
	int a,n,i,j,t,s=0,q=1000003;
	long x;
	scanf("%d%d",&a,&n);
	for(j=0;j<n;j++){
		scanf("%d",&t);
		for(i=31,x=1;i--;x%=q)x*=t>>i&1?x*a:x;
		//後述
		s+=x;
	}
	printf("%d",s%q);
	return 0;
}

やっていることは先程と同じで、例えばa^19を計算するなら2進数展開を頭から見ていくと
0→…→0→1→10→100→1001→10011であり
これは矢印1step毎に「2倍して、必要なら1を足す」となっているので
対応する累乗の計算は「平方して、必要ならaを掛ける」となる

最初の読み込みを工夫して、単純な短縮

q=1e6+3,s,c,i;
long x;
main(t){
	for(c=atoi(gets(&c));~scanf("%d",&t);s+=x)for(i=31,x=1;i--;x%=q)x*=t>>i&1?x*c:x;
	c=!printf("%d",s%q);
}

130B

メモ

yukicoderでゆるふわgolf

yukicoder No.16 累乗の加算