神必题 uria

发表于 | 分类于

Description

给定正整数\(n\)，求有多少有序数对\((a, b)\)满足：

  • \(a + b\leq n\)。
  • \(a + b\mid b\)。

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

Solution

考虑不互质的数对可能很麻烦……因此我们提取\(d = \gcd(a, b)\)，将数对表示为\((a'b, b'd)\)，此时必有\(a'\perp b’\)。

然后化一下式子得到： \[ \begin{aligned} d(a' + b')&\mid a'b'd^2\\ a'+b'&\mid a'b'd \end{aligned} \] 注意到\(\gcd(a' + b', a') = \gcd(b', a') = 1\)，同理\(\gcd(a' + b', b') = 1\)，因此\(a' + b'\)只能是\(d\)的约数了。

据此我们可以设\(d = k(a' + b')\)，带入\(a + b\leq n\)得\(k(a' + b')^2\leq n\)，因此有\(a' + b'\leq\sqrt{n}\)。我们枚举\(i = a' + b'\)，那么\(d\)的数量就和\(k\)一样都是\(\lfloor\frac{n}{i^2}\rfloor\)种。

然后考虑知道了\(i\)之后怎么知道分解为互质有序数对的方案数。注意到确定了\(a'\)就确定了整个数对，而且我们知道\(\gcd(a' + b', a') = \gcd(b', a') = 1\)，因此必有\(a'\perp i, a< i\)，所以数对的方案数为\(\varphi(i)\)。

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
#include <cstdio>
const int N = 10000000;
typedef long long ll;

bool vis[N + 5]; int prm[N + 5];
ll phi[N + 5];
void process() {
  phi[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi[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) {
        phi[v] = phi[i] * (ll)prm[j]; break;
      } else {
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
}

int main() {
  process();
  ll n; scanf("%lld", &n);
  ll ans = 0;
  for(ll i = 2; (i * i) <= n; i ++) {
    ll xi = n / (i * i);
    ans += phi[i] * xi;
  }
  printf("%lld\n", ans);
  return 0;
}