不同的直线
|
考虑所有满足$0\le a,b,c\le N$的整点$(a,b,c)$。
从原点$O(0,0,0)$引直线穿过其它整点，记$D(N)$为所有不同直线的数目。
已知$D(10^6)=831909254469114121$。求$D(10^10)$的前九位和后九位数字相连所得的十八位数。
|
本题难度:
|
解答
|
给定范围内的非零整点共有$(N+1)^3-1$个，将这些点按$\gcd(a,b,c)$的值分成若干组，则有
\begin{align*}
(N+1)^3-1&=\sum_{d=1}^N|\{(a,b,c): 0\le a,b,c\le N, (a,b,c)\neq 0,\gcd(a,b,c)=d\}| \\
&=\sum_{d=1}^N|\{(a,b,c)| 0\le a,b,c \le\lfloor\frac{N}{d}\rfloor,(a,b,c)\neq(0,0,0),\gcd(a,b,c)=1\}|\\
&=\sum_{d=1}^ND(\frac{N}{d})
\end{align*}
从而得递推式
$$D(N)=(N+1)^3-1-\sum_{d=2}^ND(\frac{N}{d}).$$
递归计算即得结果$831907372805129931$。
注：以下代码使用cache装饰器作记忆化搜索，因此为Python 3代码，本题数据量较大，需要若干分钟运行。
from functools import *
target=10**10
@cache
def D(n):
t=(n+1)*(n+1)*(n+1)-1
a=2
while a<=n:
b=n//(n//a)
t-=D(n//a)*(b-a+1)
a=b+1
return t
s=str(D(target))
print(s[:9]+s[-9:])
|
| |
