Last Digits(0)

問題の概要は
http://d.hatena.ne.jp/tanakh/20060321#p1
を見ていただくとして、tanakhさんの予想が成り立たない例外を簡単に書いておく。

要はi=1の場合はb%10^nが出力だからあえて計算する必要がないということと、b%10が0になる場合、n<=7に限って言えばi=1以外のときはすべて0になるということ。これらの処理だけ加えて、0
p(a,b,m){
unsigned long long t,u;
if(b==0)return 1;
t=p(a,b/2,m)%m;
u=(t*t)%m;
return b%2?(u*a)%m:u;
}

f(b,i,m){return i?p(b,f(b,i-1,m),m):1;}

main(b,i,j){
int t,m=pow(10,7); //digit 7だけ計算
puts(" b i ans");
puts("---------------");
for(b=1;b<=100;++b){
for(i=1;i<=100;++i){
if(i==1)t=b;
else if(b%10==0)t=0;
else t=f(b,i,m);
printf("%3d %3d %7d\n",b,i,t);
}
}
}

これを実行してみると、10000通り中に同じ値が多数あることに気が付く。

つづく