Slr的比赛 xMinh搬书

题意：两摞书分别有a本和b本，每一次操作从较多的一堆中拿出与较少一堆相等的书放到较少一堆中，问k次操作后较少一堆有多少书($a,b,k<=1e9$) 对于如此大的数据范围，显然需要一些结论 通过手算直接模拟可以发现 第k次操作之后会有$2^k-1$种情况 且一定会有一种情况中包含$2^k*a$这一项 开大脑洞可以发现，所有情况中的数对$(a+b)$取模之后其实是一样的 所以答案就是$min(ans,a+b-ans)$ 其中$ans=2^k*a\%(a+b)$ ~~怕不是又一个小凯的疑惑233~~ ``` #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int a,b,k,p; ll quickpow(ll n,ll k) { ll s=1; while (k) { if (k&1) s=s*n%p; n=n*n%p; k>>=1; } return s; } int main() { scanf("%d%d%d",&a,&b,&k); p=a+b; if (!a) {puts("0"); return 0;} ll ans=quickpow(2,k)%p*a%p; printf("%lld\n",min(ans,p-ans)); return 0; } ```