yukicoder No.251 大きな桁の復習問題(1)

問題はこちら
No.251 大きな桁の復習問題(1) - yukicoder

やることはyukicoder No.167 N^M mod 10 - メモと同じ
N^Mをmod pで求めるのには
Nはmod pの情報が
Mはオイラーの定理(あるいはフェルマーの小定理)からmod p-1の情報があれば良い
N,Mとも巨大な数なので文字列として受け取って処理する

（以下ではN,Mと書けば与えられた数を、n,mと書けばプログラム中の変数を指す）

int p=129402307;
long pow(long a,long m){
	if(m==0)return 1;
	if(m%2==0)return pow(a*a%p,m/2);
	return pow(a*a%p,m/2)*a%p;
}
int main(){
	long n=0,m=0,i;
	char s[100010];
	gets(s);
	for(i=0;s[i];i++)n=(n*10+s[i]-48)%p;
	//Nの読み込み。nにはN%pが入る
	gets(s);
	for(i=0;s[i];i++)m=(m*10+s[i]-48)%(p-1);
	//Mの読み込み。mにはM%(p-1)がはいる
	if(strlen(s)==1&&s[0]=='0'){puts("1");return 0;}
	//Mが0ならNによらずN^Mは1
	if(n==0){puts("0");return 0;}
	//Mが0でなく、かつnが0ならn^Mはmod pで0
	//powの実装を上のように行っている場合、この分岐をしないと
	//M≠0かつm=0かつN=0のとき、pow(0,0)で1が返ってしまう
	printf("%ld",pow(n,m));
	//n,Mが共に非0なら通常のpow
	return 0;
}

縮める

n,m,i,x,y,p=129402307;
main(t){
	for(;i=getchar()-10;x++)n=(n*10+i-38)%p;
	for(;i=getchar()-10;y++)m=(m*10+i-38)%~-p;
	//xにNの桁数、yにMの桁数が入る
	for(i=27;i--;)t=1L*t*t%p*(m>>i&1?n:1)%p;
	//pow(n,m)の計算
	n=!printf("%d",n?t:y==1&&m==0);
	//nが非0なら通常のpow、nが0ならMが0の時に限り1でさもなくば0
}

読み込みが2つに分かれてるのがいただけない

//単純に
for(;read(0,&i,1);i-10?f?m=(m*10+i-48)%~-p,y++:(n=(n*10+i-48)%p,x++):f++);
//とまとめられるので、これを縮めて
for(;read(0,&i,1);i-10?m=(m*10+i-48)%(p-f),y++:!f++?n=m,x=y,y=m=0:0);
//更にxとyをまとめて
for(;read(0,&i,1);i-10?m=(m*10+i-48)%(p-f),s+=f:!f++?n=m,m=0:0);
//mへの代入をくくりだして
for(;read(0,&i,1);m=i-10?s+=f,(m*10+i-48)%(p-f):!f++?n=m,0:m);

以上をまとめると

p=129402307,n,m,f,s,i;
main(t){
	for(;read(0,&i,1);m=i-10?s+=f,(m*10+i-48)%(p-f):!f++?n=m,0:m);
	for(i=27;i--;)t=1L*t*t%p*(m>>i&1?n:1)%p;
	i=!printf("%d",n?t:s==!m);
}

159B