draid's blog

By draid, history, 11 days ago,

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;
}

• 0

 » 11 days ago, # | ← Rev. 2 →   0 Two changes: G(n/i) can overflow so instead use G((n/i)%MOD) Subtraction in modulo doesn't work as in math with C++ instead of res -= (G(t)*t)%MOD do res += MOD - (G(t)*t)%MOD
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 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?
 » 11 days ago, # |   0 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$.
 » 11 days ago, # |   0 Overflow