快速幂

快速幂"/>

快速幂

撞杆子的CC学姐
描述

17级学姐中有个学姐，人称撞杆子的CC，因为CC学姐走路的时候总是在低头玩手机，所以经常撞杆子，在一次把鼻子撞破后，CC学姐在想自己出一次门究竟要撞多少个杆子。一天CC学姐打算去广场玩，已知CC学姐走完全程共撞n次杆子，CC学姐第一次撞杆子时是走了1米的时候，每次撞完杆子后潜意识都会改变自己的小心程度，即第i次撞杆子后经过2i % 107米后会撞下一个杆子，现在CC学姐想知道自己走了多远。

格式

输入格式

输入一个n(1 <= n <= 10^5),CC学姐走完全程要撞的杆子数量

输出格式

输出一个s，CC学姐走完全程所走的距离

样例

样例输入 Copy
1
3
4

样例输出 Copy
1
7
15
本题是一道简单的快速幂取模，知道（AB）%M=（A%MB%M）%M，基本上就可以解出来了。
一般法：

int fun(int a,int n)
{int i;int t=1;for(i=1;i<=n;i++)t=t*a;return t;} 

这种方法简单，但时间复杂度大，做题时容易时间超限。
递归法：
思路：当n为奇数时，2ⁿ=2^(n-1)/2*2^(n-1)/2*2
当n为偶数时，2ⁿ=2^n/2*2^n/2

 long long int fun(long long int a,long long int b,long long int m)
{long long int t=1;if(b==0) return 1;//2^0=1if(b%2){t=a;return a*fun(a,b-1,m)%m;}long long int k=fun(a,b/2,m)%m;return (t*k)%m*k%m;
}

在贴上代码：

#include<stdio.h>
#include<math.h>
long long int fun(long long int a,long long int b,long long int m)
{long long int t=1;if(b==0) return 1;if(b%2){t=a;return a*fun(a,b-1,m)%m;}long long int k=fun(a,b/2,m)%m;return (t*k)%m*k%m;
}
int main()
{long long int n;while(~scanf("%d",&n)){long long int sum=0;long long int k=0;while(n)//n为撞杆子总数，当n为0时，就是CC学姐走的总路程{sum=sum+fun(2,k,107);n--;k++;}printf("%lld\n",sum);}return 0;
}