読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.167 N^M mod 10

問題はこちら
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