D - Sum
Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u
Output
2
Hint
1. For N = 2, S(1) = S(2) = 1.
2. The input file consists of multiple test cases.
Hint
1. For N = 2, S(1) = S(2) = 1.
2. The input file consists of multiple test cases.
思路:
首先根据规律找出sum=2^(n-1),转化为求
2^(n-1)%mod
利用费马小定理a^b%c=a^(b%(c-1))%c
所以解决这个问题只需要两部
1.用大数取余求得(N-1)%mod-1
2.用快速幂求得a^b%mod
ac代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#define mod 1000000007
using namespace std;
char a[10000005];
long long quickmod(long long a, long long b)
{
long long ans=1;
while(b)
{
if(b&1)
{
ans=(ans*a)%mod;
}
b=b/2;
a=(a*a)%mod;
}
return ans;
}
int main()
{
long long sum,len;
while(gets(a))
{
len=strlen(a);
sum=0;
for(int i=0;i<len;i++)
{
sum=(sum*10+a[i]-'0')%(mod-1);
}
if(sum==0)
cout<<quickmod(2,mod-2)<<endl;
else
{sum--;
cout<<quickmod(2,sum)<<endl;}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)