[BZOJ2956]模积和

  ∑∑((n mod i) * (m mod j))  1<=i<=n, 1<=j<=m, i≠j
= ∑(n mod i) * ∑(m mod i) - ∑((n mod i) * (m mod i))
= ∑(n-[n/i]*i) * ∑(m-[m/i]*i) - ∑(nm-([n/i]+[m/i])i+[n/i][m/i])

然后就分块暴力了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <cstdio>
#include <algorithm>

const long long MOD = 19940417;
inline long long sumsqr(const long long n) { return n * (n+1) % MOD * (2*n+1) % MOD * 23263820 % MOD; }
long long calc(const long long n, const long long k)
{
  long long res = 0;
  for (long long i = 1, last; i <= n; i = last+1)
  {
    last = std::min(n, k/(k/i));
    (res += (k/i) * (i+last) % MOD * (last-i+1) % MOD * 29910626 % MOD) %= MOD;
  }
  return res;
}
long long n, m;
int main()
{
  scanf("%lld%lld", &n, &m);
  if (n < m) std::swap(n, m);
  long long ans = (n*n-calc(n, n)) % MOD * ((m*m-calc(m, m)) % MOD);
  (ans += -m * m % MOD * n % MOD + calc(m, n) * m % MOD + calc(m, m) * n % MOD) %= MOD;
  for (long long i = 1, last; i <= m; i = last+1)
  {
    last = std::min(m, std::min(n/(n/i), m/(m/i)));
    (ans += -(n/i) * (m/i) % MOD * ((sumsqr(last) - sumsqr(i-1)) % MOD) % MOD) %= MOD;
  }
  printf("%lld", (ans%MOD+MOD)%MOD);
}

Comments