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