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

Вывести ответ по модулю
Автор Kane, 10 лет назад, По-русски

Решаю задачу Сумма квадратов с e-olimp. Что не так в этом куске кода? Подозреваю что ошибка во взятии по модулю.

cin >> n >> m;

if (n < 0 && m < 0) {

n = abs(n);

  m = abs(m);

}

if (n > m) swap(n, m);

long long sum1 = 0, sum2 = 0, gr, GR;

gr = abs(n);

if (n > 0)

--gr;

sum1 = ((MOD + (gr * (gr + 1) * (2 * gr + 1) / 6) % MOD) % MOD);

GR = abs(m);

sum2 = ((MOD + (GR * (GR + 1) * (2 * GR + 1) / 6) % MOD) % MOD);

ll ans;

if (n > 0)

ans = (MOD + (sum2 - sum1) % MOD) % MOD;

else

ans = (MOD + (sum2 + sum1) % MOD) % MOD;

assert(ans >= 0);

cout << ans;

cout << '\n';

UPD: Прошу прощения за кривую разметку

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
gr * (gr + 1) * (2 * gr + 1)

При больших значениях gr происходит переполнение int64. Надо модули более узко расставить.

a = gr % MOD
b = (gr + 1) % MOD
с = (2 * gr + 1) % MOD
sum = (((a * b) % MOD) * c) % MOD

Ещё некорректно делить по модулю. Надо умножать на делитель возведённый в степень MOD - 2.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    Последнее предложение верно, только если MOD простое число. Более правильно сказать, что следует домножать на обратный(по модулю MOD) к делителю(к шестёрке) элемент. Если MOD не взаимно прост с 6, то нужно извращаться: например для каждого числа помнить сколько раз в его разложении на простые множители присутсвует 2 и 3, и остаток от деления на MOD / НОД(MOD, 6).

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

      Можно же проще, если я не ошибаюсь. Хотя бы одно из этих чисел(gr,gr+1,2*gr+1) будет делиться на 2. Аналогичное утверждение верно для 3. И можно соответствующие числа изначально(до перемножения) поделить на 2(3). А дальше просто перемножить по модулю.

      → Ответить