【问题背景】 有马公主长时间不弹钢琴，现在钢琴上蒙了一层灰…… 【问题描述】 钢琴上摆放着两摞书，总共有 c 本，初始时左边一摞有 a 本，右边一摞有 c-a 本，满足 1 ≤ a < c，保证 c 是奇数。 有马公主要进行 b 次操作，每次操作分两种情况，假设左边的书有 x 本： 1.左边的书的数目小于右边的书时，即 x < c-x，从右边的书中取出 x 本放到 左边，使左边有 x*2 本书； 2.右边的书的数目小于左边的书时，即 x>c-x，从左边的书中取出 c-x 本放 到右边，使右边有(c-x)*2 本书。 请问经过 b 次这样的操作后，左边有多少本书？ 【输入格式】 从文件 boyne.in 中读入数据。 读入一行三个整数 a，b，c，含义见题目描述。 对于所有数据，保证1≤a < c≤1000000000,1≤b≤1000000000，c 为奇数。 【输出格式】 输出到文件 boyne.out 中。 输出 1 行 1 个整数，表示 b 次操作后左边有多少本书。
【样例输入】 3 3 7 【样例输出】 3
【子任务】
分析： 每一道没有一眼秒的题，要做的第一件事就是打暴力
然后我们就会发现暴力中有一个优美的if语句 if (x < c-x) x=2*x; else x=2*x-c;
把if的判断移一下项，就会变成 if (2*x < c) x=2*x; else x=2*x-c;
这个-c好生烦人 但是看起来又有一种熟悉之感 没错，减操作在一定意义上就相当于%
如果a==1，那么答案就是2^b%c 那要是a!=1怎么办，通过实际计算可以发现 答案就是a*2^b%c
这里写代码片 #include<cstdio> #include<cstring> #include<iostream> #define ll long long using namespace std; ll a,b,c; void KSM() { ll t=1,num=2; while (b) { if (b&1) t=(t*num)%c; b>>=1; num=(num*num)%c; } t=(t*a)%c; printf("%lld",t); } int main() { freopen("boyne.in","r",stdin); freopen("boyne.out","w",stdout); scanf("%lld%lld%lld",&a,&b,&c); KSM(); return 0; }