Project Euler 388

题目

Distinct Lines

Consider all lattice points \((a,b,c)\) with \(0 \le a,b,c \le N\).

From the origin \(O(0,0,0)\) all lines are drawn to the other lattice points.

Let \(D(N)\) be the number of distinct such lines.

You are given that \(D(1 000 000) = 831909254469114121\).

Find \(D(10^{10})\). Give as your answer the first nine digits followed by the last nine digits.

解决方案

令\(N=10^{10}\)。

在这个三维空间中，一共有\((N+1)^3-1\)个点，其坐标满足\(\max(a,b,c)>0\)。

在这些点中，如果一个点不被前面的点"阻挡"，当且仅当其坐标满足\(\gcd(a,b,c)=1\)。

那么有：

\[\begin{aligned} (N+1)^3-1&=|\{(a,b,c)|0\le a,b,c\le N,\max(a,b,c)>0\}|\\ &=\sum_{d=1}^N|\{(a,b,c)|0\le a,b,c\le N,\max(a,b,c)>0,\gcd(a,b,c)=d\}|\\ &=\sum_{d=1}^N\left|\left\{(a,b,c)| 0\le a,b,c \le \left\lfloor\dfrac{n}{d}\right\rfloor,\max(a,b,c)>0,\gcd(a,b,c)=1\right\}\right|\\ &=\sum_{d=1}^ND\left(\dfrac{n}{d}\right) \end{aligned}\]

那么我们可以得到关于\(D\)的递推式，直接使用数论分块的方式进行求解即可：

\[D(N)=(N+1)^3-1-\sum_{d=2}^N D\left(\dfrac{n}{d}\right)\]

代码

本代码使用了GMP库实现。

# include <bits/stdc++.h>
# include "gmpxx.h"
using namespace std;
typedef long long ll;
const ll N=1e10;
const int M=1000000;
const int O = 9;

mpz_class d[M+2];
unordered_map<ll,mpz_class>mpD;
mpz_class D(ll n) {
    if (n <= M && d[n] > 0) return d[n];
    else if (n > M && mpD.count(n)) return mpD[n];
    mpz_class w = mpz_class(n+1)*(n+1)*(n+1) - 1;
    for (ll l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        w -= D(n / l) * (r - l + 1);
    }
    if (n <= M) return d[n] = w;
    else return mpD[n] = w;
}
int main() {
    mpz_class ans2 = D(N);
    string s = ans2.get_str();
    string ans = s.substr(0, O) + s.substr(max(0, int(s.size()) - O));
    cout << ans << endl;
}