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(1000000)=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{array}{rl}(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|\{(a,b,c)|0\le a,b,c\le \lfloor {\displaystyle \frac{n}{d}}\rfloor ,max(a,b,c)>0,gcd(a,b,c)=1\}\right|\\ & =\sum _{d=1}^{N}D\left({\displaystyle \frac{n}{d}}\right)\end{array}$$

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

$$D(N)=(N+1{)}^3-1-\sum _{d=2}^{N}D\left({\displaystyle \frac{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;
}