BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ dby (猪的天空之猪很郁闷) 于 (Tue Nov 28 07:24:03 2006) 提到: 题目意思是给出N和素数P，求杨辉三角第N行中能被P整除的数的个数。结论是将N写成P进制数N0N1N2....Nm，答案就是(N+1)-(N0+1)*(N1+1)*...(Nm+1)。证明如下: 组合数C(n,m)=n!/(m!(n-m)!)不被被素数P整除的充要条件是n!含有因子P的个数等于m!和(n-m)!含有因子P的个数之和。对任意正整数n，n!含有的素数因子P的个数为n/p+n/p^2+n/p^3......那么当且仅当满足 n/p+n/p^2+....=m/p+m/p^2+... + (n-m)/p+(n-m)/p^2+.... (1)时C(n,m)才不被P整除。 (1)等价于对任意i都有n/p^i=m/p^i+(n-m)/p^i (2) (2)又等价于 m%(p^i)<=n%(p^i) (3)对任意正整数i都成立。将n和m分别写成P进制数 n0,n1,n2,n3,n4,.... m0,m1,m2,m3,m4,.... 容易得到(3)成立的充要条件就是 m0<=n0, m1<=n1 .... 所以m的可取值个数就是(n0+1)*(n1+1)*(n2+1)...... ☆─────────────────────────────────────☆ moyuji (moyuji) 于 (Tue Nov 28 09:10:51 2006) 提到: ... ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Tue Nov 28 09:54:02 2006) 提到: 似乎都是猜的 ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Tue Nov 28 10:13:46 2006) 提到: 不过还是看不懂 ☆─────────────────────────────────────☆ dby (猪的天空之猪很郁闷) 于 (Tue Nov 28 13:57:08 2006) 提到: 挺有道理的~ 当时也推到他的3个条件了，不过没往进制那想…… 【在 sunmoonstar 的大作中提到: 】 : 似乎都是猜的 ☆─────────────────────────────────────☆ xiaoming (月下明) 于 (Tue Nov 28 14:49:32 2006) 提到: 1)等价于对任意i都有n/p^i=m/p^i+(n-m)/p^i (2) (2)又等价于 m%(p^i)<=n%(p^i) 我只是不明白从１怎么到２，不会推 ☆─────────────────────────────────────☆ dby (猪的天空之猪很郁闷) 于 (Wed Nov 29 18:49:10 2006) 提到: 把n化成p进制数 Pn-1……p0 那么n包含的p因子个数为 p0*0,p1*1,p2*(1+p),p3*(1+p+p^2); 把m，n-m也化成p进制数，假设某一位上的数字m>n那么必存在进位因为m+n-m=n. 由于 k*(1+p+p^2+...p^q)>k1*(1+p+..p^(q-1))+k2*(1+p+...+p*(q-1)) 这里k1+k2=k; 所以推出（1）跟（2）等价。【在 xiaoming 的大作中提到: 】 : 1)等价于对任意i都有n/p^i=m/p^i+(n-m)/p^i (2) : (2)又等价于 m%(p^i)<=n%(p^i) : 我只是不明白从１怎么到２，不会推

[合集] 2006上海I题的结论及证明