Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 3980    Accepted Submission(s): 1620

Problem Description  

 

Sample Input 2  

 

Sample Output 2 Hint 1. For N = 2, S(1) = S(2) = 1. 2. The input file consists of multiple test cases.  

 

Source 2013 Multi-University Training Contest 10  

 

Recommend zhuyuanchen520     一道学长教的数论题。找出规律后发现求的是2^(n-1)。 利用费马小定理欧拉降幂 由于n非常大，可采用字符串读入，读入同时分位取余(((a*100%MOD)+b*10%NOD)+c%MOD)%MOD，最后跑一边快速幂。 注意n-1，MOD-1 适用于Java大数超时的情况。 -------------------------------------------------------------- ps:后续。竟然成为了18年网络赛的原题...     #include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<string> #include<math.h> #include<queue> #include<stack> #include<map> #include<set> #include<vector> #include<algorithm> #define MAX 1000005 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; ll qMod(ll a,ll b){ ll ans=1; while(b>0){ if(b&1) ans=ans*a%MOD; b>>=1; a=a*a%MOD; } return ans; } int main() { int n,len,i; char s[MAX]; while(~scanf(" %s",s)){ ll c=0; len=strlen(s); for(i=0;i<len;i++){ int x=s[i]-'0'; c=c*10+x; if(c>1000000006) c%=1000000006; } c=((c-1)%1000000006+1000000006)%1000000006; printf("%lld\n",qMod(2,c)); } return 0; }

 

转载于:https://www.cnblogs.com/yzm10/p/8748094.html

相关资源：数据结构—成绩单生成器