1234：2011

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 7002 ??? 通過數: 2979

【題目描述】

已知長度最大為200位的正整數n，請求出2011^n的后四位。

【輸入】

第一行為一個正整數k，代表有k組數據（k≤200），接下來的k行，每行都有一個正整數n，n的位數≤200。

【輸出】

每一個n的結果為一個整數占一行，若不足4位，去除高位多余的0。

【輸入樣例】

3 5 28 792

【輸出樣例】

1051 81 5521

【分析】

? ? ? ? 依題意，求2011^n的后四位。后四位顯然是模10000。2011^n%10000，可以直接套用蒙哥馬利冪取模模板。

模板1：蒙哥馬利冪取模（非遞歸）

冪取模 a^b mod n 非遞歸 long long mod_exp(long long a,long long b,long long n) {long long res=1;while(b){if(b&1)res=res*a%n;a=a*a%n; // 反復平方b>>=1; // 2分求冪}return res; }

?模板很好理解，用到的就是反復平方法和二分求冪法，例如：求(2^100)%10的最后一位是多少？

(2^100)%10 = (4^50)%10 = (16^25)%10 = (16%10)^25%10 = (6^25)%10 = (6*6^24)%10 = (6*36^12)%10 = ... = 6。

模板2：蒙哥馬利冪取模（遞歸1）

冪取模 m^n mod p 遞歸1 long long mod_exp(long long m,long long n,long long p) {long long t;if(n==1)return m%p;t=mod_exp(m,n/2,p)%p;t=t*t%p;if(!(n&1)) // 等價 if(n%2==0)return t;elsereturn m*t%p; }

模板3：蒙哥馬利冪取模（遞歸2）

冪取模 m^n mod p 遞歸2 long long mod_exp(long long m,long long n,long long p) {long long t;if(n==1)return m%p;if(n%2==0)return mod_exp( (m*m)%p , n/2 , p);elsereturn m*mod_exp(m%p, n-1, p)%p; }

?【參考代碼】

#include<stdio.h> #include<string.h> #define MAXN 210char s[MAXN];//蒙哥馬利冪取模非遞歸模板 long long quickpow(long long a,long long b,long long n) // a^b mod n {long long res=1;while(b) //2分求冪法 {if(b & 1)res=res*a%n;a=(a*a)%n; //反復平方法 b>>=1;}return res; } int main() {int i,k,len,n;scanf("%d",&k);getchar();while(k--){gets(s);n=0;len=strlen(s);n=s[len-1]-'0';if(len>=2)n+=(s[len-2]-'0')*10;if(len>=3)n+=(s[len-3]-'0')*100;if(len>=4)n+=(s[len-4]-'0')*1000;n%=500;printf("%lld\n",quickpow(2011,n,10000));}return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1234

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1234：2011）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。