撞杆子的cc学姐

杆子的cc学姐"/>

撞杆子的cc学姐

撞杆子的cc学姐(第一次写博客大家见谅）

描述

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

输入格式

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

输出格式

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

样例输入

1
3
4

样例输出

1
7
15

#include<stdio.h>
#include<math.h>
int f(int a,int b){
int i;
int sum=1;
a=a%107;
while(b>0)
{if(b%2==1)//判断是否为奇数幂
sum=(sum*a)%107;//奇数幂单独提出来乘
b=b/2;//降幂
a=(a*a)%107;//例如: a^4=（a*a）*（a*a）=（a*a)^2所以当a^b=（a*a）^(b/2)//注意这里的 b是大于等于2的偶数。}
return sum;}
main()
{
int n,i;
long long int s;
while(~scanf("%d",&n))
{ s=i=0;
while(n>0){s=s+f(2,i);n--;//将杆子数减去，到 0则跳出。i++;}
printf("%lld\n",s);
}
}

一道很简单的快速幂取余题目，要明白 ( A * B ) % P = ( A % P * B % P ) % P;

                                  要是有不对的地方请在评论区讨论我加以改正