LibreOJ 6052 「雅礼集训 2017 Day11」DIV

发表于 | 分类于

Description

定义复数\(a + bi\)为\(k\)的约数，当且仅当\(a, b\)为整数且存在整数\(c, d\)满足\((a + bi)(c + di) = k\)。

给定\(n\)，求\(1\)到\(n\)中所有整数的实部大于\(0\)的约数的实部的和。

答案模1004535809。

\(n\leq 10^{10}\)。

Solution

为啥这题和某课件上的简化版差距这么大啊……

考虑一个复数\((a + bi)(c + di) = k\)意味着什么，其实也就是下面两个式子： \[ ac - bd = k\\ ad + bc = 0 \] 由第二个式子可得： \[ \frac{a}{b} = -\frac{c}{d} \] 那么我们考虑将\(a, b\)约去他们两个之间的最大公约数，\(c, d\)也做一样的操作。那么上式还是成立的，并且等号两边的分式都已经最简化了，因此此时有\(a = c, b = -d\)。

带回最早的式子（两个复数的积那个）可以得到： \[ c(a^2 + b^2) = k \] 这个\(c\)是我们先前约去的常数的积。从此式也可以看出\((a^2+b^2)|k\)，并且贡献一定是\(a\)乘上一个常数。

那么我们枚举互质数对\((a, b)\)，其对答案的贡献是\(a\sigma(\frac{n}{a^2 + b^2})\)（这里\(\sigma\)表示\(\sigma_1\)，即约束之和）。

因此最终答案为： \[ \begin{aligned} \quad&\sum_{i = 1}^n\sum_{a\perp b, (a^2 + b^2) | i} a\sigma(\frac{i}{a^2+b^2}) \end{aligned} \] 这玩怕不是几乎不可做……因此我们考虑枚举\(k = a^2 + b^2\)： \[ \begin{aligned} \quad&\sum_{k = 1}^n\sum_{a\perp b, a^2 + b^2 = k} a\sum_{k | i}\sigma(\frac{i}{k})\\ =&\sum_{k = 1}^n\sum_{a\perp b, a^2 + b^2 = k} aD(\lfloor\frac{n}{k}\rfloor)\\ =&\sum_{k = 1}^nD(\lfloor\frac{n}{k}\rfloor)\sum_{a\perp b, a^2 + b^2 = k} a\\ =&\sum_{k = 1}^nD(\lfloor\frac{n}{k}\rfloor)f(k) \end{aligned} \] 其中\(D\)为\(\sigma\)的前缀和，\(f(k)\)表记的是啥可以根据上下文推导一下（逃

这个形式几乎和杜教筛如出一辙……像杜教筛一样先大力数论分块，然后先考虑怎么处理\(D\)，很显然有一个\(O(\sqrt{n})\)的做法： \[ \sum_{i = 1}^n i\lfloor\frac{n}{i}\rfloor \] 如此一来我们可以考虑先预处理不大于\(n^\frac{2}{3}\)的\(D\)值，其他情况用上面的式子求（甚至不需要记忆化复杂度也是对的）。用杜教筛那种复杂度证明可以证出这部分的复杂度是\(O(n^\frac{2}{3})\)的。

然后我们发现我们其实也要处理\(f​\)的前缀和\(F​\)……但是有个互质在这这个玩意并不好处理。那么我们考虑类似于狄利克雷卷积的一些思路？定义一个\(G(x) = \sum_{1\leq a^2+b^2\leq x}a​\)，这个东西可以很方便的用\(O(\sqrt{n})​\)的复杂度求（\(G(x)=\sum_{i = 1}^{\lfloor\sqrt{x}\rfloor}i\lfloor\sqrt{x - i^2}\rfloor​\)），然后我们发现有： \[ G(x) = \sum_{i = 1}^{\lfloor\sqrt{x}\rfloor}iF(\lfloor\frac{x}{i^2}\rfloor) \] 然后这个还是有点像杜教筛的一些形式啊！我们发现我们要抽出来的事\(F(x)\)，因此移一下项就有了： \[ F(x)=G(x) - \sum_{i = 2}^{\lfloor\sqrt{x}\rfloor}iF(\lfloor\frac{x}{i^2}\rfloor) \] 还是如出一辙的处理套路啊……对于大于\(n^\frac{2}{3}\)的情况我们直接用这个式子\(O(\sqrt{n})\)求（顺便记忆化）；其他情况就要考虑预处理了，那么我们考虑预处理\(f(x)\)本身，这个东西可以通过枚举\(a\)然后枚举\(b\)最后判断是否互质的搞法在\(O(n^\frac{2}{3}\log n)\)的复杂度里搞出来。总复杂度证明还是和杜教筛如出一辙。

然后做完了？其实并没有。我们上面钦点了复数虚部为正整数。至于负整数和正整数的情况对称，答案完全一致。如果虚部为\(0\)的话那么参与运算的全都是正整数，因此此时答案就是\(D(n)\)了。

Code

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
const int N = 5000000;
using ll = long long;
const ll ha = 1004535809LL;
ll d[N + 5], f[N + 5];
int prm[N + 5]; bool vis[N + 5];
int gcd(int a, int b) {
  if(!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
void sieve() {
  int cnt = 0;
  vis[1] = true; d[1] = 1; f[1] = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      d[i] = i + 1; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        d[v] = d[i] * d[prm[j]] - (ll)prm[j] * d[i / prm[j]];
        break;
      } else {
        d[v] = d[i] * d[prm[j]];
      }
    }
  }
  for(int i = 1; i * i <= N; i ++) {
    for(int j = 1; j * j + i * i <= N; j ++) {
      if(gcd(i, j) == 1) {
        f[j * j + i * i] += i;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    d[i] = (d[i] + d[i - 1]) % ha;
    f[i] = (f[i] + f[i - 1]) % ha;
  }
}

std::unordered_map<ll, ll> ma_d;
ll S(ll n) {
  static const ll inv_2 = 502267905LL;
  ll ret = ((n % ha) * ((n + 1) % ha)) % ha;
  ret = (ret * inv_2) % ha;
  return ret;
}
ll sigma(ll n) {
  if(n <= (ll)N) return d[n];
  if(ma_d.count(n)) return ma_d[n];
  ll ret = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll delta = (S(next) - S(i - 1) + ha) % ha;
    delta = (delta * ((n / i) % ha)) % ha;
    ret = (ret + delta) % ha;
    i = next + 1LL;
  }
  ma_d[n] = ret;
  return ret;
}
std::unordered_map<ll, ll> ma_f;
ll calc_f(ll n) {
  if(n <= (ll)N) return f[n];
  if(ma_f.count(n)) return ma_f[n];
  ll ret = 0;
  for(ll i = 1; i * i <= n; i ++) {
    ll delta = floor(sqrt(n - i * i));
    delta %= ha; delta = (delta * i) % ha;
    ret = (ret + delta) % ha;
  }
  for(ll i = 2; i * i <= n; i ++) {
    ll delta = (calc_f(n / (i * i)) * i) % ha;
    ret = (ret - delta + ha) % ha;
  }
  ma_f[n] = ret;
  return ret;
}
ll calc(ll n) {
  ll ret = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll th = calc_f(next);
    ll delta = (th - las + ha) % ha;
    delta = (delta * sigma(n / i)) % ha;
    ret = (ret + delta) % ha;
    las = th; i = next + 1LL;
  }
  return ret;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", (calc(n) * 2LL + sigma(n)) % ha);
  return 0;
}