i was trying to solve this cool cses problem the other minute and i stumbled across a problem relating modulo: im pretty sure there is nothing wrong with my usage of spoiler dirichlet's hyperbola method, basically what i did was computing the first two sums modulo M then subtracting the last chunk modulo then modulo the actual result applying the rule (a mod m) — (b mod m) mod m = (a — b mod m), but there is a case when b mod m is just greater than a mod m and not b > a, i don't know what to do! can anyone please correct my usage of modulo! thanks in advance :3
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int G(int n) {
return n*(n+1)/2;
}
signed main() {
int n; cin >> n;
int res = 0, MOD = 1e9 + 7, t = (int)sqrt(n);
for(int i = 1; i <= t ; i++) {
res += G(n/i)%MOD;
res += (i * (n/i))%MOD;
res %= MOD;
}
res -= (G(t)*t)%MOD;
res %= MOD;
cout << res;
}
Two changes:
G(n/i)can overflow so instead useG((n/i)%MOD)res -= (G(t)*t)%MODdores += MOD - (G(t)*t)%MODCode: https://cses.fi/paste/6a1435305a277a1a97b09b/
yay (this works!) thanks for the response! :3 on a side note are you aware of any blog that actually list such cases of bad mod'ing/common mistakes?
The problem is that you are using division incorrectly. When you want to find the result in a certain modulus and you need to divide, you must use the modular inverse.
One of the simplest ways to obtain the modular inverse is by using Fermat's Little Theorem, which states: $$$a^p \equiv a \pmod{p}$$$
Since $$$p$$$ is prime we can multiply both sides by $$$a^{p-2}$$$ resulting in: $$$ a^{p-2} \equiv a^{-1} \pmod{p} $$$
We can obtain the modular inverse by computing $$$a^{p-2}$$$. This can be done using binary exponentiation in $$$O(\log p)$$$
In some cases, binary exponentiation might be too slow, and you can precompute the modular inverses up to a certain $$$n$$$.
Overflow