The Battle of Brains

northwolves

9# zgg___


这个似乎很简单，2p吧

mathe

设p和q都是质数，且p=2q-1，如果p很大，比方说大约在10^12附近，如何快速的求出Mod(Binomial(p,q),p^2)的值？
zgg___ 发表于 2011-1-11 17:07

这个不难，首先可以知道$p|C_p^q$,所以我们只需要计算${C_p^q}/p={(p-1)!}/{q!(p-q)!} (mod p)$
其次$(p-q)! =1*2*...*(p-q)-=(-1)^{p-q}(p-1)(p-2)*...*q (mod p)-=(p-1)(p-2)*...*q(mod p)$
所以${C_p^q}/p=1/q(mod p)=2(mod p)$
也就是最后结果是2p

mathe

其实这里q的素性没有用到，只要q是奇数就应该可以。
而如果q改成偶数，那么结果就是(p-2)p了

zgg___

谢谢大家的回复，但是真是抱歉呢，因为题目写错了。
题中Mod(Binomial(p,q),p^2)应为Mod(Binomial(p,q),p^3)，当然也可以是Mod(Binomial(p,q)/p,p^2)。

zgg___

也可以是相当于求Mod[Sum(1/k,{k,1,q-1}),p]，但是还是没有什么办法。

mathe

$(p-1)(p-2)*..*(p-(p-q)) -= -(1+2+...+(p-q))*p+(p-q)! -=-{q(q-1)}/2p+(p-q)! (mod p^2)$
于是
${(p-1)!}/{q!(p-q)!}-={-{q(q-1)}/2p+(p-q)!}/{q(p-q)!}-=(-{q-1}/{2(q-1)!}p+1/q)(mod p^2)$
于是主要问题就变成求$(q-1)!(mod p)$
我们可以知道$((q-1)!)^2-=(p-1)! -=-1(mod p)$
于是我们知道$(q-1)!(mod p)$是-1的平方根，而-1的平方根总共有两个，也就是说，我们需要确定到底是哪一个平方根。

zgg___

To mathe 16层:
最顶上的式子的第一个等号是为什么呢?
将左面式子展开后，p的一次项为什么是那样子的呢?

zgg___

恩，已经解决了，呵呵。

mathe

呵呵,还不知道是那个平方根,你是如何解决的?

zgg___

终于完成了所有的14题和3个奖分题了，呵呵。
每个奖分题都得的是250分，后来才看到有这个的，呜呜。
不过第1名还是很牛的，他的3个奖分题只用了36.3分钟。