51Nod-1013 3的幂的和 (快速幂)

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

Output示例

40
注意事项就最后的奇偶性

 1 #include<stdio.h>
 2 int poww(long long a,long long b)
 3 {
 4     long long ans=1,base=a;
 5     while (b!=0)
 6     {
 7         if(b&1!=0)
 8         {
 9             ans*=base;
10             ans=ans%1000000007;
11         }
12         base*=base;
13         base=base%1000000007;
14         b>>=1;
15     }
16     return ans;
17 }
18 int main()
19 {
20     long long N;
21     scanf("%lld",&N);
22     long long s=poww(3,N+1);
23     if(s%2!=0)//需要判断奇偶性，如果s为奇数（s-1）则为偶数，则可以整出2，则不需要加1000000007；
24     s=(s-1)/2;
25     else//如果s为偶数，则（s-1)为奇数，则需要加上1000000007才能使其能整除2
26     s=(s-1+1000000007)/2;
27     printf("%lld
",s);
28     return 0;
29 }