Блог пользователя draid

Автор draid, история, 5 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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/

  • »
    »
    5 месяцев назад, # ^ |
    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?

»
5 месяцев назад, # |
  Проголосовать: нравится 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$$$.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Overflow