题目大意
小A和小B都是小吃货。
身为小吃货，最重要的事情当然是吃啦！所以他们正在纠结如何分芝麻吃。
一开始，小A有$n$个芝麻，小B有$m$个芝麻。
因为他们都想吃更多芝麻，所以每次手中芝麻较少的人就会拿走另一个人的芝麻，使得自己的芝麻变成原来的$2$倍那么多。如果两个人芝麻一样多，那么小A会拿走小B的芝麻使得他的芝麻变成原来的$2$倍。
经过$k$次这样的行动之后，小A和小B都累了，所以他们准备开始吃芝麻了。
身在一旁的小C想知道，小A和小B中吃的较少的那个人吃了多少芝麻呢？
题目分析
进行一次操作后情况有可能变成$(2a,b-a)$或$(a-b,2b)$。
再进行一次操作后情况可能变成$(4a,b-3a)$或$(3a-b,2b-2a)$或$(2a-2b,3b-a)$或$(a-3b,4b)$。
如此不断重复，但是不难发现二元组的第一项加上第二项始终等于$n+m$，实际上操作是在模$n+m$的意义下不断地乘$2$，用快速幂计算即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL n,m,k;
LL Quick_Pow(LL a,LL b,LL mod) {
LL sum=1;
while(b) {
if(b&1)sum=sum*a%mod;
a=a*a%mod;
b>>=1;
}
return sum;
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
printf("%lld\n",min(n*Quick_Pow(2,k,n+m)%(n+m),m*Quick_Pow(2,k,n+m)%(n+m)));
return 0;
}
|
