神刀安全网

欧拉计划 : 531. 中国剩余定理

题目

Problem 531: Chinese leftovers

Let g(a,n,b,m) be the smallest non-negative solution x to the system:

x = a mod n

x = b mod m

if such a solution exists, otherwise 0.

E.g. g(2,4,4,6)=10, but g(3,4,4,6)=0.

Let φ(n) be Euler’s totient function.

Let f(n,m)=g(φ(n),n,φ(m),m)

Find ∑f(n,m) for 1000000 ≤ n < m < 1005000

解答

这题相当容易,直接使用中国剩余定理即可,但要注意 n 和 m 可能不是互素的。正好 PARI/GP 的 chinese 函数能够处理这种情况。我们有以下 PARI/GP 程序:

g(a,n,b,m)=iferr(lift(chinese(Mod(a,n),Mod(b,m))),E,0) h(z,c)={z--;my(v=vector(c,i,eulerphi(z+i))); sum(m=2,c,sum(n=1,m-1,g(v[n],z+n,v[m],z+m)))} print(h(1000000,5000));quit() 

这个程序的运行时间是 15 秒。

参考资料

  1. Wikipedia: Chinese remainder theorem
  2. 图灵社区:PARI/GP 简介

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 欧拉计划 : 531. 中国剩余定理

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址