如何在没有整数溢出的情况下找到 n%(k*k)？

Question

我知道 (a*b)%m 等于 ((a%m)*(b%m))%m?

但是a%(m*m)怎么计算呢？

Answer 1

我们需要在不引起整数溢出的情况下计算a%(m*m)。

long long int a, m, sqrt_a, ans;
sqrt_a = sqrt(a);
if (sqrt_a < m) {
    ans = a; // since "m > sqrt_a" then a%(m*m) will be "a"
}
else {
   ans = a % (m*m); // since "m <= sqrt_a" then m*m won't cause overflow
}