Project Euler 325

发表于 分类于 阅读次数： 本文字数： 8k 阅读时长 ≈ 7 分钟

Project Euler 325

题目

Stone Game II

A game is played with two piles of stones and two players. On each player’s turn, the player may remove a number of stones from the larger pile. The number of stones removed must be a positive multiple of the number of stones in the smaller pile.

E.g. Let the ordered pair \((6,14)\) describe a configuration with \(6\) stones in the smaller pile and \(14\) stones in the larger pile, then the first player can remove \(6\) or \(12\) stones from the larger pile.

The player taking all the stones from a pile wins the game.

A winning configuration is one where the first player can force a win. For example, \((1,5)\), \((2,6)\), and \((3,12)\) are winning configurations because the first player can immediately remove all stones in the second pile.

A losing configuration is one where the second player can force a win, no matter what the first player does. For example, \((2,3)\) and \((3,4)\) are losing configurations: any legal move leaves a winning configuration for the second player.

Define \(S(N)\) as the sum of \((x_i + y_i)\) for all losing configurations \((x_i, y_i), 0 \lt x_i \lt y_i \le N\).

We can verify that \(S(10) = 211\) and \(S(10^4) = 230312207313\).

Find \(S(10^{16}) \bmod 7^{10}\).

解决方案

局面是 \((x,y)\)，满足 \(0<x<y\)。一次操作：从大堆 \(y\) 中减去 \(k x\)，其中 \(k\ge 1\) 且 \(k x\le y\)。若减成 \(0\) 则立刻获胜，否则重排成新的有序对 \((x',y')\)。

把 \(y\) 对 \(x\) 做除法：\(y=qx+s, q=\left\lfloor \dfrac{y}{x}\right\rfloor\ge 1, 0\le s<x.\)

  • 若 \(s=0\)（即 \(x\mid y\)），玩家可以选 \(k=q\) 直接把 \(y\) 减成 \(0\)，立刻赢。 所以所有 \(s=0\) 都是必胜态。

  • 若 \(s>0\)，合法的 \(k\) 是 \(1,2,\dots,q\)：

    • 选 \(k<q\)：新大堆仍 \(\ge x\)，新局面变成 \((x,y-kx)\)；
    • 选 \(k=q\)：新大堆变成 \(s<x\)，重排后新局面是 \((s,x)\)。

可见，这就是欧几里得算法的减法版一步：不是从 \((x,y)\to (y\bmod x,x)\)，而是允许先做几次减法再决定是否交换。

令比值\(r=\dfrac{y}{x}\in(1,\infty).\)

当 \(1<r<2\) 时，必有 \(q=1\)，也就是 \(y=x+s\)（\(0<s<x\)）。此时合法操作只有 \(k=1\)，而且必然发生交换：$ (x,x+s)(s,x).$

新比值为\(r'=\dfrac{x}{s}=\dfrac{1}{\frac{x+s}{x}-1}=\dfrac{1}{r-1}.\)

当 \(r\in(1,2)\) 时，这一步没有任何选择：只能取走一次小堆大小，局面比值被强制变换为\(T(r)=\dfrac{1}{r-1}.\)

因此在区间 \((1,2)\) 上，胜负判定完全由迭代 \(r\rightarrow T(r)\) 的行为决定；这正是后续会出现临界点的根源（由于\(T(r)\)在\((1,2)\)上单调递减，临界点有且仅有一个）。另一方面，当 \(r>2\) 时玩家可以选择合适的整数 \(k\) 将比值一次压回 \((1,2)\)（或在 \(r\) 为整数时直接获胜），所以整个游戏的核心分析会反复落在 \((1,2)\) 这段“被迫变换”上。

我们希望存在一个临界值 \(\alpha\in(1,2)\)，使得：

  • 当 \(1<r<\alpha\) 时，这类局面是必败（因为唯一一步把对手送到必胜区）；
  • 当 \(\alpha<r<2\) 时，这类局面是必胜（因为唯一一步把对手送到必败区）。

临界值之下之所以是必败态，是因为当 \(r\) 足够接近 \(1\) 时，强制变换 \(T(r)=\dfrac{1}{r-1}\) 会变得非常大，往往直接跳出区间 \((1,2)\) 并落到一个明显的必胜区域（例如为整数的局面）。由于在 \((1,2)\) 内走法唯一，当前玩家无法避免把对手送入必胜态，因此这样的 \(r\) 本身必然是必败态。

在 \((1,2)\) 内只有一步可走，所以“必败/必胜”要靠 \(T\) 的去向来切分。最自然的“分界点”就是 \(T\) 把它映回自己 的点：如果 \(r=\alpha\) 时 \(T(r)=r\)，那么 \(T\) 在该点两侧一定把区间对换（因为 \(T\) 在 \((1,2)\) 上严格递减且连续）。

于是令\(\alpha = T(\alpha)=\dfrac{1}{\alpha-1}.\)解得\(\alpha=\dfrac{1+\sqrt5}{2}\)。这就是黄金比例 \(\varphi\)。

并且因为 \(T\) 在 \((1,2)\) 上递减，且 \(T(\varphi)=\varphi\)，立刻得到：

  • 若 \(1<r<\varphi\)，则 \(T(r)>\varphi\)；
  • 若 \(\varphi<r<2\)，则 \(T(r)<\varphi\)。

因此在 \((1,2)\) 内的输赢已经被迫确定为：当 \(1<\dfrac{y}{x}<\varphi\) 时必败；当 \(\varphi<\dfrac{y}{x}<2\) 时必胜。

接下来证明 全局定理：

对任意整数局面 \((x,y)\)（\(0<x<y\)），它是必败态当且仅当\(\dfrac{y}{x}<\varphi\)。

当\(q=1\)，即\(r\in (1,2)\)时，可见

  • 若 \(r<\varphi\)，唯一一步到 \(T(r)>\varphi\)（对手必胜），所以当前必败；
  • 若 \(r>\varphi\)，唯一一步到 \(T(r)<\varphi\)（对手必败），所以当前必胜。

当\(q\ge 2\)，即 \(r\ge 2\)时，可以写成\(y=qx+s, q\ge 2,0<s<x, r=q+\dfrac{s}{x}.\)

我们将展示：总能一步走到必败区 \(y'<\varphi x'\)。

注意 \(\varphi\) 满足\(\varphi-1=\frac{1}{\varphi}.\)

那么有两种候选走法：

  1. 选 \(k=q-1\)，新局面为 \((x,x+s)\)（因为 \(y-(q-1)x=x+s\) 且仍 \(\ge x\)），新比值\(r_1=\dfrac{x+s}{x}=1+\dfrac{s}{x}.\) 它落入必败区当且仅当\(1+\dfrac{s}{x}<\varphi\Longleftrightarrow\dfrac{s}{x}<\varphi-1=\dfrac{1}{\varphi}\Longleftrightarrow s<\dfrac{x}{\varphi}.\)

  2. 选 \(k=q\)，新局面为 \((s,x)\)（交换），新比值\(r_2=\dfrac{x}{s}.\)它落入必败区当且仅当\(\dfrac{x}{s}<\varphi\Longleftrightarrow s>\dfrac{x}{\varphi}.\)

因为 \(\varphi\) 无理数，\(s\) 不可能恰好等于 \(\dfrac{x}{\varphi}\)，所以上述两条件必有一个成立：

  • 若 \(s<\dfrac{x}{\varphi}\)，走法 1 直接送入必败区；
  • 若 \(s>\dfrac{x}{\varphi}\)，走法 2 直接送入必败区。

因此所有 \(q\ge 2\) 的局面都是必胜态。

综上，全局定理成立：

  • \(y<\varphi x\)（且 \(y>x\)）必败；
  • \(y>\varphi x\) 必胜；
  • \(x\mid y\) 也必胜（是 \(y>\varphi x\) 的特例之外，但不冲突）。

令\(N=10^{16}\)，那么必败态满足\(x<y\le N, y<\varphi x.\)

对每个 \(x\)，可取的 \(y\) 是\(x+1,\dots,\min(N,\lfloor \varphi x\rfloor).\)令\(U_x=\min(N,\lfloor \varphi x\rfloor).\)

则\(S\displaystyle{(N)=\sum_{x=1}^{N-1}\sum_{y=x+1}^{U_x} (x+y).}\)

设\(K=\left\lfloor\dfrac{N}{\varphi}\right\rfloor.\)当 \(x\le K\) 时 \(\lfloor\varphi x\rfloor\le N\)，所以 \(U_x=\lfloor\varphi x\rfloor\)；当 \(x>K\) 时 \(U_x=N\)。

于是\(\displaystyle{S(N)=S_1+S_2,S_1=\sum_{x=1}^{K}\sum_{y=x+1}^{\lfloor\varphi x\rfloor} (x+y),S_2=\sum_{x=K+1}^{N-1}\sum_{y=x+1}^{N} (x+y).}\)化简后得：

\[S_2=\dfrac{(N-K-1)(N-K)(N+K+1)}{2}.\]

接下来计算\(S_1\)。利用 \(\varphi^2=\varphi+1\) 得\(\lfloor\varphi x\rfloor=\left\lfloor x+\dfrac{x}{\varphi}\right\rfloor= x+\left\lfloor\dfrac{x}{\varphi}\right\rfloor.\)

记\(t_x=\left\lfloor\dfrac{x}{\varphi}\right\rfloor.\)则对 \(x\le K\)，\(y\) 从 \(x+1\) 到 \(x+t_x\)，共有 \(t_x\) 项：\(\displaystyle{\sum_{y=x+1}^{x+t_x}(x+y)=\frac{t_x(4x+t_x+1)}{2}=\frac{4xt_x+t_x^2+t_x}{2}.}\)

因此

\[ S_1=\sum_{x=1}^{K}\frac{4xt_x+t_x^2+t_x}{2}=2\sum_{x=1}^{K}x t_x+\frac12\sum_{x=1}^{K}(t_x^2+t_x). \]

所以只要能快速计算\(\displaystyle{F(K)=\sum_{x=1}^{K} t_x,V(K)=\sum_{x=1}^{K} x t_x,U(K)=\sum_{x=1}^{K} t_x^2}\)，就有\(S_1=2V(K)+\dfrac{U(K)+F(K)}{2}.\)

定义\(g(n)=\left\lfloor\dfrac{n+1}{\varphi}\right\rfloor.\)（在 OEIS A005206 中，\(g\) 与Zeckendorf 右移是同一个对象的等价描述。则\(t_x=g(x-1)\)。

于是

\[\begin{aligned} &F(K)=\sum_{x=1}^{K}t_x=\sum_{i=0}^{K-1}g(i),\\ &U(K)=\sum_{i=0}^{K-1}g(i)^2,\\ &V(K)=\sum_{x=1}^{K}xg(x-1)=\sum_{i=0}^{K-1}(i+1)g(i)=\sum_{i=0}^{K-1}i g(i)+\sum_{i=0}^{K-1}g(i). \end{aligned}\]

因此只要能求

\[ G(n)=\sum_{i=0}^{n}g(i), H(n)=\sum_{i=0}^{n} g(i), Q(n)=\sum_{i=0}^{n} g(i)^2, \]

就有

\[ F(K)=G(K-1), U(K)=Q(K-1), V(K)=H(K-1)+G(K-1). \]

接下来开始用的是“黄金比的 Beatty/Zeckendorf 对应性质”的一个非常实用形式：

取 Zeckendorf 用的斐波那契数列 \(F_0=1;F_1=2;F_{k}=F_{k-1}+F_{k-2} (k\ge 2).\)

在第297题，我们介绍过Zeckendorf 定理：任意正整数 \(n\) 可唯一写成若干个互不相邻的 \(F_k\) 之和。

对函数 \(g(n)=\left\lfloor\dfrac{n+1}{\varphi}\right\rfloor\)，有下面的性质：

若 \(F_k\le n< F_{k+1}\)，令 \(n=F_k+r\)，则 Zeckendorf 保证 \(0\le r < F_{k-1}\)，因此在 Zeckendorf 表示里，\(F_k\) 这一项不会和 \(r\) 的表示发生“相邻冲突/进位合并”（\(r\) 只能用到 \(F_{k-2}\) 及更小的项）。因此\(n\)的Zeckendorf 表示为\(\displaystyle{n = F_k + \sum_j F_{i_j}, i_j\le k-2.}\)

那么对 Zeckendorf 表示做右移就得到\(\displaystyle{g(n)=F_{k-1}+\sum_j F_{i_j-1}=F_{k-1}+g(r)}\)，即\(g(F_k+r)=F_{k-1}+g(r)\)。

设 \(n=F_k+r\)（\(0\le r<F_{k-1}\)）。区间 \([0,n]\) 分成两段：

  • \([0,F_k-1]\)：这是一个“整块端点”，我们可以预处理其 \(G,H,Q\)；
  • \([F_k,F_k+r]\)：写成 \(F_k+j\)（\(0\le j\le r\)），用性质 \(g(F_k+j)=F_{k-1}+g(j)\) 逐项展开。

于是，为计算 \(\displaystyle{G(n)=\sum_{i=0}^n g(i)}\)，那么有：

\[ \sum_{j=0}^r g(F_k+j)=\sum_{j=0}^rl(F_{k-1}+g(j)r)=(r+1)F_{k-1}+G(r), \]

所以有关于\(G\)的递推式：

\[ G(n)=G(F_k-1)+(r+1)F_{k-1}+G(r). \]

为计算 \(\displaystyle{H(n)=\sum_{i=0}^n i g(i)}\)，那么对 \(i=F_k+j\)：有\(i g(i)=(F_k+j)(F_{k-1}+g(j))=F_kF_{k-1}+F_k g(j)+jF_{k-1}+j g(j).\)

求和得

\[ \sum_{j=0}^r i g(i) =(r+1)F_kF_{k-1}+F_k G(r)+F_{k-1}\frac{r(r+1)}{2}+H(r), \]

所以有关于\(H\)的递推式：

\[ H(n)=H(F_k-1)+(r+1)F_kF_{k-1}+F_k G(r)+F_{k-1}\frac{r(r+1)}{2}+H(r). \]

为计算 \(\displaystyle{Q(n)=\sum_{i=0}^n g(i)^2}\)，那么\(\displaystyle{g(F_k+j)^2=(F_{k-1}+g(j))^2=F_{k-1}^2+2F_{k-1}g(j)+g(j)^2.}\)

求和得

\[ \sum_{j=0}^r g(F_k+j)^2=(r+1)F_{k-1}^2+2F_{k-1}G(r)+Q(r), \]

所以有关于\(Q\)的递推式：

\[ Q(n)=Q(F_k-1)+(r+1)F_{k-1}^2+2F_{k-1}G(r)+Q(r). \]

把 \(F_k-1\) 自身再按 \(F_k=F_{k-1}+F_{k-2}\) 分段，就能得到端点数组 \(G(F_k-1),H(F_k-1),Q(F_k-1)\) 的递推。

令\(G_k=G(F_k-1), H_k=H(F_k-1), Q_k=Q(F_k-1).\)把 \([0,F_k-1]\)拆成两段：\([0,F_k-1]=[0,F_{k-1}-1] \cup [F_{k-1},F_k-1].\)

那么计算递推 \(G_k\)时，第二段用 \(n=F_{k-1}+r\)：

\[\sum_{n=F_{k-1}}^{F_k-1} g(n)=\sum_{r=0}^{F_{k-2}-1}(F_{k-2}+g(r))=F_{k-2}^2+G(F_{k-2}-1).\]

所以

\[ G_k=G_{k-1}+G_{k-2}+F_{k-2}^2. \]

那么计算递推 \(Q_k\)时，也是类似的：

\[ \sum_{n=F_{k-1}}^{F_k-1} g(n)^2 =\sum_{r=0}^{F_{k-2}-1}l(F_{k-2}+g(r)r)^2 =\sum_{r=0}^{F_{k-2}-1}(F_{k-2}^2+2F_{k-2}g(r)+g(r)^2). \]

于是

\[ \sum_{n=F_{k-1}}^{F_k-1} g(n)^2 =F_{k-2}\cdot F_{k-2}^2 + 2F_{k-2}G_{k-2}+Q_{k-2} =F_{k-2}^3+2F_{k-2}G_{k-2}+Q_{k-2}. \]

计算递推 \(H_k\)时，有：

第二段： \[ \begin{aligned} \sum_{n=F_{k-1}}^{F_k-1} ng(n)&=\sum_{r=0}^{F_{k-2}-1} (F_{k-1}+r)(F_{k-2}+g(r))\\ &=\left[F_{k-2}\sum_{r=0}^{F_{k-2}-1}(F_{k-1}+r)\right] + \left[\sum_{r=0}^{F_{k-2}-1}(F_{k-1}+r)g(r)\right]\\ &=\left[F_{k-2}^2F_{k-1}+\frac{F_{k-2}^2(F_{k-2}-1)}{2}\right] + \left[F_{k-1}G_{k-2}+H_{k-2}\right]\\ &=F_{k-2}^2F_{k-1}+\frac{F_{k-2}^2(F_{k-2}-1)}{2}+F_{k-1}G_{k-2}+H_{k-2}. \end{aligned} \]

因此 \[H_k=H_{k-1}+H_{k-2}+F_{k-1}G_{k-2}+F_{k-2}^2F_{k-1}+\frac{F_{k-2}^2(F_{k-2}-1)}{2}.\]

自此所有递推完成计算过程已经完成。

代码

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
from bisect import bisect_right
from functools import lru_cache

# ------------------------------------------------------------
# Project Euler 325: Stone Game II
# 目标：计算 S(10^16) mod 7^10
# ------------------------------------------------------------
N = 10 ** 16
MOD = 7**10  # 282475249

# ------------------------------------------------------------
# 1) Zeckendorf 用 Fibonacci 序列：F0=1, F1=2, Fk=Fk-1+Fk-2
#    这套序列的特点：任何正整数都有唯一的“非相邻表示”
# ------------------------------------------------------------
def build_fibs(limit: int):
    """
    构造 Zeckendorf 用的 Fibonacci：
      fib[0]=1, fib[1]=2, fib[k]=fib[k-1]+fib[k-2]
    直到 fib[-1] > limit 为止（保证覆盖分解需要）。
    """
    fib = [1, 2]
    while fib[-1] <= limit:
        fib.append(fib[-1] + fib[-2])
    return fib

# ------------------------------------------------------------
# 2) 关键函数 g(n) = floor((n+1)/phi) 的“Zeckendorf 右移”计算
#
#    性质：若 n = sum fib[i_j]（无相邻），则
#      g(n) = sum shift(fib[i_j])
#    其中 shift(fib[k]) = fib[k-1]，并且约定 shift(fib[0]=1) = 1。
#
#    这允许完全不用浮点数（避免 sqrt5/phi 的精度问题）。
# ------------------------------------------------------------
def g_zeck(n: int, fib) -> int:
    """
    返回 g(n) = floor((n+1)/phi)，用 Zeckendorf 表示右移实现。
    """
    if n < 0:
        return 0
    rem = n
    ans = 0
    k = bisect_right(fib, n) - 1  # 最大 fib[k] <= n

    # 贪心取 Zeckendorf：取了 fib[k] 后下一项不能取 fib[k-1]，所以 k -= 2
    while k >= 0:
        if fib[k] <= rem:
            rem -= fib[k]
            # shift：fib[k] -> fib[k-1]；k==0 时约定 shift(1)=1
            ans += fib[k - 1] if k > 0 else 1
            k -= 2
        else:
            k -= 1
    return ans

# ------------------------------------------------------------
# 3) 三个前缀和：
#    G(n) = sum_{i=0..n} g(i)
#    H(n) = sum_{i=0..n} i*g(i)
#    Q(n) = sum_{i=0..n} g(i)^2
#
#    对 n=F_k + r (0<=r<F_{k-1}) 有递推：
#      g(F_k+j) = F_{k-1} + g(j)
#
#    从而：
#      G(n)=G(F_k-1) + (r+1)*F_{k-1} + G(r)
#      H(n)=H(F_k-1) + (r+1)*F_k*F_{k-1} + F_k*G(r) + F_{k-1}*r(r+1)/2 + H(r)
#      Q(n)=Q(F_k-1) + (r+1)*F_{k-1}^2 + 2F_{k-1}*G(r) + Q(r)
#
#    所以需要预处理端点：
#      G_end[k]=G(F_k-1), H_end[k]=H(F_k-1), Q_end[k]=Q(F_k-1)
# ------------------------------------------------------------
def precompute_endpoints(fib):
    """
    预处理 G(F_k-1), H(F_k-1), Q(F_k-1)。
    用 fib[k]=fib[k-1]+fib[k-2] 分段：
      [0..F_{k-1}-1] 与 [F_{k-1}..F_k-1]
    后一段用同样的 g(F_{k-1}+j)=F_{k-2}+g(j) 展开即可。
    """
    m = len(fib)
    G_end = [0] * m
    H_end = [0] * m
    Q_end = [0] * m

    # k=0: F_0=1 => n=0，仅 g(0)=floor(1/phi)=0
    G_end[0] = 0
    H_end[0] = 0
    Q_end[0] = 0

    # k=1: F_1=2 => n=1，g(0)=0, g(1)=floor(2/phi)=1
    G_end[1] = 1
    H_end[1] = 1   # 0*g(0) + 1*g(1) = 1
    Q_end[1] = 1   # g(0)^2 + g(1)^2 = 1

    for k in range(2, m):
        # 记 A=F_{k-1}, B=F_{k-2}, 且 F_k = A + B
        A = fib[k - 1]
        B = fib[k - 2]

        # G: 后一段长度 B，每项多了常数 B（因为 shift 后是 F_{k-2}=B）
        # Σ_{j=0..B-1} (B + g(j)) = B*B + G_end[k-2]
        G_end[k] = G_end[k - 1] + B * B + G_end[k - 2]

        # H: Σ (A+j)*(B+g(j))
        # = B*Σ(A+j) + A*Σ g(j) + Σ j g(j)
        # Σ(A+j)=B*A + B(B-1)/2
        segH = (
            B * (B * A + B * (B - 1) // 2)
            + A * G_end[k - 2]
            + H_end[k - 2]
        )
        H_end[k] = H_end[k - 1] + segH

        # Q: Σ (B+g(j))^2 = Σ(B^2 + 2B g(j) + g(j)^2)
        segQ = B * B * B + 2 * B * G_end[k - 2] + Q_end[k - 2]
        Q_end[k] = Q_end[k - 1] + segQ

    return G_end, H_end, Q_end

def make_GHQ(limit: int):
    """
    构造 fib，并返回一个可在 O(log n) 求 (G(n),H(n),Q(n)) 的函数。
    """
    fib = build_fibs(limit)
    G_end, H_end, Q_end = precompute_endpoints(fib)

    def shift_value(k: int) -> int:
        # 对应 g(F_k + r) = shift(F_k) + g(r)
        # shift(F_0=1)=1，其余 shift(F_k)=F_{k-1}
        return fib[k - 1] if k > 0 else 1

    @lru_cache(maxsize=None)
    def GHQ(n: int):
        """
        返回 (G(n), H(n), Q(n))，其中：
          G(n)=Σ_{i=0..n} g(i)
          H(n)=Σ_{i=0..n} i g(i)
          Q(n)=Σ_{i=0..n} g(i)^2
        """
        if n <= 0:
            # n=0 时 g(0)=0，所以三个都是 0
            return (0, 0, 0)

        k = bisect_right(fib, n) - 1      # 最大 F_k <= n
        r = n - fib[k]                    # n = F_k + r，且 0<=r<F_{k-1}
        Gr, Hr, Qr = GHQ(r)
        s = shift_value(k)                # s = shift(F_k)

        # G(n)=G(F_k-1) + (r+1)*s + G(r)
        G = G_end[k] + (r + 1) * s + Gr

        # H(n)=H(F_k-1)
        #     + Σ_{j=0..r}(F_k+j)*(s+g(j))
        #     = H_end[k] + (r+1)*F_k*s + F_k*G(r) + s*Σj + H(r)
        H = (
            H_end[k]
            + (r + 1) * fib[k] * s
            + fib[k] * Gr
            + s * (r * (r + 1) // 2)
            + Hr
        )

        # Q(n)=Q(F_k-1) + (r+1)*s^2 + 2s*G(r) + Q(r)
        Q = Q_end[k] + (r + 1) * s * s + 2 * s * Gr + Qr

        return (G, H, Q)

    return fib, GHQ

# ------------------------------------------------------------
# 4) S2 的 O(1) 求和辅助：区间和与平方和
# ------------------------------------------------------------
def sum_range(a: int, b: int) -> int:
    """Σ_{x=a..b} x"""
    if a > b:
        return 0
    return (a + b) * (b - a + 1) // 2

def sumsq_range(a: int, b: int) -> int:
    """Σ_{x=a..b} x^2"""
    if a > b:
        return 0
    def S2(n: int) -> int:
        return n * (n + 1) * (2 * n + 1) // 6
    return S2(b) - S2(a - 1)

# ------------------------------------------------------------
# 5) 计算 S(N)
#    1) K = floor(N/phi) = g(N-1)
#    2) 用 GHQ 得到 G,H,Q，从而得到 F,FM,FF
#    3) S1 = 2*FM + (FF+F)/2
#    4) S2 用闭式
# ------------------------------------------------------------
def S(N: int) -> int:
    # GHQ 的 fib 需要覆盖到 N 的量级即可
    fib, GHQ = make_GHQ(N + 5)

    # K = floor(N/phi) = g(N-1)
    K = g_zeck(N - 1, fib)

    # t_x = floor(x/phi) = g(x-1)
    # F(K)=Σ_{x=1..K} t_x = Σ_{i=0..K-1} g(i) = G(K-1)
    # FM(K)=Σ x t_x = Σ (i+1)g(i) = H(K-1)+G(K-1)
    # FF(K)=Σ t_x^2 = Σ g(i)^2 = Q(K-1)
    Gk, Hk, Qk = GHQ(K - 1)
    F = Gk
    FM = Hk + Gk
    FF = Qk

    # S1 = Σ_{x=1..K} (4x t_x + t_x^2 + t_x)/2
    S1 = 2 * FM + (FF + F) // 2
    S2 = (N - K - 1) * (N - K) * (N + K + 1) // 2 % MOD
    return (S1 + S2) % MOD

# ------------------------------------------------------------
# 6) 输出题目要求：S(10^16) mod 7^10
# ------------------------------------------------------------

ans = S(N) % MOD
print(ans)