题解 | #快速乘#

常规的快速乘算法如下：

#include <cstdio>
using namespace std;

int main() {
     long long q,a, b,p;
     scanf("%lld",&q);
     while (q--) {
         scanf("%lld%lld%lld",&a,&b,&p);
         long long res=0;
         while (b) {
             if(b&1)res=(res+a)%p;
             a=(a+a)%p;
             b=b>>1;
		 }
         res%=p;
         printf("%lld\n",res);
    }
}
// 64 位输出请用 printf("%lld")

但是题目要求是只能用加法（减法也算在内）和取模，所以要将b&1和b>>1换成加法和取模的表示方法。b>>1可以换成减法，即减去权重base，让b的后部分全为0；判断某位是否为1，只需要用高一位的权重取模，如果结果不为0，则该位为1。

		long long res = 0, base=1;
        while (b) {
            if (b % (base + base) != 0) {
                res = (res + a) % p;
                b -= base;
            }
            a = (a + a) % p;
            base=base+base;
        }
        res %= p;
        printf("%lld\n", res);
    }
}