700. 欧拉币(Eulercoin)
莱昂哈德·欧拉出生于1707年4月15日，所以让我们考虑以下序列：
$$ 1504170715041707n \bmod 4503599627370517 $$该序列中的某个元素被定义为欧拉币，当且仅当它严格小于之前已经定义的所有欧拉币。如，序列的第一项是\(1504170715041707\)，这是第一枚欧拉币；第二项是\(3008341430083414\)，因为它大于\(1504170715041707\)，所以它不是欧拉币。序列的第三项是\(8912517754604\)，比第一项要小，因此是一枚新的欧拉币。因此，前两枚欧拉币之和为\(1513083232796311\)。求所有欧拉币之和。
分析：这道题实际上与求两个数的最大公约数的欧几里德算法有关，也叫做辗转相除法。具体而言，为求数\(a,b(a>b)\)的最大公约数\(gcd(a,b)\)，设\(a=qb+r\)，则\(gcd(a,b)=gcd(b,r)\)。通过这种方式我们可把求解两个较大数的最大公约数的问题转化为求解两个较小数的公约数问题。对于这道题目我们可以采取类似的思路。
对于题目中的问题，我们实际上要求解\(ax\ mod\ b\)，其中\(a<b\)且\(gcd(a,b)=1\)。当\(x=1\)时，我们得到第一个欧拉币\(c_1=a\)，而之后的欧拉币需满足\(c_k<c_{k-1}\)。设\(ax\)对\(b\)取余的结果为\(c\)，则显然有\(ax-by=c\)。这是一个线性丢番图方程，当\(c\)可以整除\(gcd(a,b)\)时有解，因\(gcd(a,b)=1\)，所以这个方程是有解的。为了解这个方程，我们可以使用欧几里得算法，因为\(b>a\)，则：
$$
\begin{aligned}
-b & =-q_{1} a+c_{1}\\
-a & =-q_{2} c_{1} +c_{2}\\
-c_{1} & =-q_{3} c_{2} +c_{3}\\
& \vdots \\
-c_{k-2} & =-q_{k} c_{k-1} +c_{k}\\
& \vdots \\
-c_{j-2} & =-q_{j} c_{j-1} +1
\end{aligned}
$$
根据欧几里得算法的性质，其中显然有\(c_1>c_2>c_3>\cdots>c_k\)，则是符合题目要求的欧拉币。从以上算法中我们还可以观察到各个欧拉币间的递推关系，即：
$$
c_k=-c_{k-2}\ mod\ c_{k-1}
$$
我们可以使用这个递推关系来求解\(c_k\)，直到\(c=1\)为止，这时我们就找到了所有的欧拉币，最后对所有欧拉币求和即可。代码如下：
# time cost = 12.8 µs ± 176 ns
def main():
c = 1504170715041707
nc = 8912517754604
res = c + nc
while nc > 0:
c,nc = nc,(-c)%nc
res += nc
return res