draid's blog

struggling to take modulo correctly
By draid, history, 5 months ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Two changes:

  1. G(n/i) can overflow so instead use G((n/i)%MOD)
  2. 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

Code: https://cses.fi/paste/6a1435305a277a1a97b09b/

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Overflow

→ Reply