ZOJ 3707 Calculate Prime S

题意：定义了S[n]为{1,2,...,n}的非连续数字的子集的个数，然后对于每个S[n]，如果对于每个1<=i<n，gcd(S[i],S[n])=1，则称S[n]是素的S。对于第k个素的S，找到一个最小的S[n]，使得S[n]是x的倍数，并且S[n]>=第k个素的S。然后输出(S[n]/x)%m。

首先证明几个结论。

I. gcd(ab,c)=gcd(a,c) 当gcd(b,c)=1时。
证明：gcd(ab,c)=gcd(a,c)*gcd(b,c)=gcd(a,c)

II. gcd(a,b)=gcd(b, a%b)。
证明：假设a>=b，则a=nb+m。假设g|a，g|b，所以g|(nb+m)，所以g|m。因为a%b=(nb+m)%b=m，所以得证。

III. gcd(fib(i),fib(i+1))=1。
证明：因为fib(i+1)=fib(i)+fib(i-1)，
所以gcd(fib(i),fib(i+1))=gcd(fib(i),fib(i)+fib(i-1))=gcd(fib(i),(fib(i)+fib(i-1))%fib(i))=gcd(fib(i),gcd(fib-1))，
可以把euclid的过程给展开，得到：
fib(i+1)=1*fib(i)+fib(i-1)
fib(i)=1*fib(i-1)+fib(i-2)
fib(i-1)=1*fib(i-2)+fib(i-3)
......
fib(4)=1*fib(3)+fib(2)
fib(3)=2*fib(2)+0
最后一行写出来就是：
2 = 2*1+0
所以gcd(fib(i),fib(i+1))=fib(2)=1;
英文原文证明以及反证法参考：
http://mathforum.org/library/drmath/view/52716.html

IV. fib(u+v)=fib(u)fib(v-1)+fib(u+1)fib(v).
证明：利用反证法。
当u=1时：fib(1+v)=fib(1)fib(v-1)+fib(2)fib(v)=fib(v-1)+fib(v) 成立。
假设u=n时成立：fib(n+v)=fib(n)fib(v-1)+fib(n+1)fib(v) 成立。
u=n+1时：
fib(n+1+v)=fib(n+v)+fib(n+v-1)=fib(n)fib(v-1)+fib(n+1)fib(v) + fib(n-1)fib(v-1)+fib(n)fib(v)
=fib(v-1)(fib(n)+fib(n-1)) + fib(v)(fib(n-1)+fib(n)) = fib(n+1)fib(v-1)+fib(n+2)fib(v) = fib(n+1+v)
所以，由数学归纳法可以得证。
英文原文证明以及Binet Formula证明参考：
http://mathforum.org/library/drmath/view/51624.html

V. fibonacci-gcd proof: gcd(fib(n),fib(m))=fib(gcd(n,m)).
证明：假设n<=m，则: gcd(fib(n),fib(m))=gcd(fib(n),fib(n+k))，由证明IV，可得：
gcd(fib(n),fib(n+k))=gcd(fib(n),fib(n)fib(k-1)+fib(n+1)fib(k))
=gcd(fib(n),(fib(n)fib(k-1)+fib(n+1)fib(k))%fbi(b))
=gcd(fib(n),fib(n+1)fib(k))，由证明III，gcd(fib(b),fib(n+1))=1，所以由证明I可得：
gcd(fib(n),fib(n+1)fib(k))=gcd(fib(n),fib(k))，所以可得：
gcd(fib(n),fib(m))=gcd(fib(n),fib(m%n))。由展开euclid算法可知，算法在gcd(fib(g),fib(0))时停止，而g=gcd(m,n)。
所以由euclid算法的定义可得gcd(fib(g),fib(0))=fib(g)。
所以得证gcd(fib(n),fib(m))=fib(gcd(n,m))
英文原文证明参考：
http://mathforum.org/library/drmath/view/61690.html

VI. (a/b)%c=(a%bc)/b 当 b|a。
证明：因为b|a，所以a=kb。
左边=(a/b)%c=(kb/b)%c=k%c。
右边=(kb%bc)/b=((k%c)b)/b=k%c。
所以得证。

VII. fibonacci的一个结论：

矩阵快速幂即可。

VIII. 又一个结论，因为x很小（x<=100），所以能在题目给定的时间内枚举到所需的S[n]。


至此，此题需要的证明已齐，只需要素数筛法预处理出所有的位数，然后再暴力枚举即可。

posted on 2013-07-24 15:17 purplest 阅读(606) 评论(0)  编辑 收藏 引用 所属分类: 数论