莱昂哈德·欧拉(Leonhard Euler)于1707年4月15日出生。

考虑序列1504170715041707n mod 4503599627370517。

如果此序列的一个元素严格小于所有先前发现的欧拉币,则将其定义为欧拉币。

例如,第一项是1504170715041707,这是第一个欧拉币。 第二项是3008341430083414,该值大于1504170715041707,因此不是欧拉币。 但是,第三项是8912517754604,它足够小,可以用作新的欧拉币。

因此,前2个欧拉币的总和为1513083232796311。

找到所有欧拉币的总和。

用黄志斌老师(https://www.ituring.com.cn/space/98916)提示的算法

#改进欧几里得算法求线性方程的x与y
def get_(a, b):
 if b == 0:
  return 1, 0
 else:
  k = a // b
  remainder = a % b
  x1, y1 = get_(b, remainder)
  x, y = y1, x1 - k * y1
 return x, y

ec=1504170715041707
last_ec=1504170715041707
m =4503599627370517

s=set()
s.add(1)

for n in range(1,2*10**8):
 a=n*ec%m
 if a<last_ec:print(n,a);last_ec=a;s.add(a)

x,y=get_(ec,m)
inv=x%m
last_inv=x%m

for i in range(2,2*10**8):
 tmp=i*inv%m
 if tmp<last_inv:
  print (tmp,i);last_inv=tmp;s.add(i)

print(s)
print(sum(s))