欧拉计划 ： 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 秒。
参考资料
- Wikipedia: Chinese remainder theorem
- 图灵社区：PARI/GP 简介
正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
