时间限制: 2 s
空间限制: 16000 KB
题目等级 : 钻石 Diamond
题目描述 Description
著名生物学家F博士发现了一种单细胞生物。
它长得像蚯蚓,分裂速度极快(每分钟一次),分裂也像蚯蚓一样,断成两段,再长成。
它很好斗,只要q只聚集在一起,就会q只一群打起来,当然都会打死。
假设一开始有1只,求a分钟后有多少只单细胞蚯蚓?
输入描述 Input Description
两个正整数A Q
输出描述 Output Description
答案
样例输入 Sample Input
4 5
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
对于50%数据,A<=20,Q<=100.
对于全部数据,A<=2*10^9,Q<=10^8.
快速幂!!!!!!!
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 int n,m;
7 int fastpow(int a,int b)
8 {
9 int r=1;
10 int base=a;
11 while(b!=0)
12 {
13 if(b%2==1)
14 r=(r*base)%m;
15 base=(base*base)%m;
16 b=b/2;
17 }
18 return r;
19 }
20 int main()
21 {
22
23 scanf("%d%d",&n,&m);
24 //n=n-1;
25 cout<<fastpow(2,n)%m;
26 return 0;
27 }