题目描述
小$K$和小$X$都是小次货。
身为小次货，最重要的事情就是次啦！所以他们正在纠结如何分芝麻次。
一开始，小$K$有$n$个芝麻，小$X$有$m$个芝麻。
因为他们都想次更多芝麻，所以每次手中芝麻较少的人就会拿走另一个人的芝麻，使得自己的芝麻变成原来的$2$倍那么多。如果两个人芝麻一样多，那么小$K$会拿走小$X$的芝麻是的他的芝麻变成原来的$2$倍。
经过$k$次这样的行动之后，小$K$和小$X$都累了，所以他们准备开始次芝麻了。
身在一旁的小$Z$想知道，小$K$和小$X$中次的较少的那个人次了多少芝麻呢？
输入格式
一行三个整数$n,m,k$。
输出格式
一行一个整数，表示答案。
样例
样例输入：
5 5 3
样例输出：
0
数据范围与提示
样例解释：
第一次行动时，小$K$拿走小$X$的芝麻$5$个，行动后小$K$有$10$个芝麻，小$X$有$0$个芝麻。
第二次和第三次行都是小$X$拿走小$K$的芝麻，但是因为他一开始没有芝麻，所以不能拿走小$K$的芝麻。
最终小$K$有$10$个芝麻，小$X$有$0$个芝麻，次的较少的人是小$X$，次了$0$个芝麻。
数据范围：
对于$30\%$的数据，$0leqslant nleqslant {10}^5,0leqslant mleqslant {10}^5,0leqslant kleqslant {10}^5$。
对于$60\%$的数据，$0leqslant nleqslant {10}^5,0leqslant mleqslant {10}^5,0leqslant kleqslant {10}^9$。
对于$100\%$的数据，$0leqslant nleqslant {10}^9,0leqslant mleqslant {10}^9,0leqslant kleqslant {10}^9$。
题解
$30\%$算法：
暴力就好了。
时间复杂度：$Theta(k)$。
期望得分：$30$分。
实际得分：$30$分。
$60\%$算法：
找寻环节，发现最多只有$min(n,m)$次就能发现循环节。
时间复杂度：$Theta(min(n,m))$。
期望得分：$60$分。
实际得分：$60$分。
找规律即可发现，无论是小$X$还是小$K$，在进行一次操作之后芝麻数量都会变为$2 imes $当前芝麻数$mod (n+m)$。
那么我们就可以用快速幂轻松求解了。
时间复杂度：$Theta(log k)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,pos;
long long qpow(long long x,long long y)
{
long long res=1;
while(y)
{
if(y&1)res=res*x%(n+m);
x=x*x%(n+m);
y>>=1;
}
return res;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
pos=qpow(2,k);
printf("%lld",min(n*pos%(n+m),m*pos%(n+m)));
return 0;
}
rp++