問題はこちら
No.167 N^M mod 10 - yukicoder
N^Mをmod10で求めるのに必要な情報を考える
Nはmod10、即ち下1桁の情報があれば良い
Mはオイラーの定理(wikipedia)によればmod4、即ち下2桁の情報があれば良い
N,Mとも巨大な数なので文字列として受け取って処理する
Mが0のケースに注意が必要
int main(){ char n[10010],m[10010]; int a,b,t; gets(n);gets(m); t=strlen(n); a=atoi(n+t-1);//下1桁 t=strlen(m); if(t==1){ b=atoi(m); if(b==0){puts("1");return 0;} //Mの値が0ならN^MはNによらず1 } else b=atoi(m+t-2);//下2桁 printf("%d",((int)pow(a,b%4+4))%10); //最大でも9の7乗程度なので精度は大丈夫 return 0; }
さてこれを縮めたい
全部まとめて読み込まなくても下2桁分の情報を持っておけば大丈夫
出力は1文字なのでputcharを使える
ということでこんなのを書いてみる
a[2],s,c; main(f){ for(;read(0,&c,1);)c-10?a[f]=a[f]%10*10+c-48,s-=f:f++; //a[0]にNの下2桁、a[1]にMの下2桁、sに(1-(Mの桁数))が入る //ループ終了時にcは10となっていることを↓で使っている c=!putchar((f=pow(*a%c,a[1]%4+(s||a[1])*4))%c+48); //powの第2引数は、Mが1桁でかつ0のときのみ0、そうでない時はM%4+4になる //powの結果を明示的にintにキャストするでのはなくfへの代入により暗にする }
これで122Bとかなり短いが、もうちょっと頑張りたい
配列で文字数を食っているのでmain再帰に書き換えてみる
c,f;main(s,a,b){
for(b=0;c=getchar()-10;s--)b=b%10*10+c-38;
//読み込んだ値の下2桁をbに保存、sには(1-(桁数))が入る
f++?f=!putchar((f=pow(a%10,b%4+(s||b)*4))%10+48):main(1,b);
//1回目は読み込んだ値を渡して再帰
//2回目は計算して出力
}
118B
