5
25
2016
0

【合集】数学公式推导与证明题目

POJ2480 longge's problem

1、\(当m与n互质时,(gcd(i,m*n)=gcd(i,m)*gcd(i,n),则gcd为积性函数\)

因为积性函数的和也为积性函数,令所求函数

$\sum_{i=1}^n\sum_{d=1}^i\sum_{t=1}^(i/d)F(d)G(t,i)$

POJ3373 Candy Distribution

序列\(a[i]=(1+i)*i/2\);是否存在一个i,使得a[1]~a[i]对N取模的值恰好覆盖0~N。

<==>序列\(A[i]=(1+i)*i/2%N\);是否存在一个i,使得A[1]~A[i]构成模N的完全剩余系。

集合A是模N的完全剩余系的充要条件:

1)A中含有N个整数

2)A中任意两个整数对N不同余

<==>是否存在两个整数x、y,使得A[x]=A[y].

<==>是否存在两个整数x、y,使\((1+x)*x/2==(1+y)*y/2 (mod N)\)

<==>\((x-y)*(x+y+1)==0 (mod N)\)

x-y与x+y+1奇偶性不同,故:

N为奇数时,上述同余式一定成立,无法构成完全剩余系

N为2的幂次时,一定不成立,构成完全剩余系

其它情况:设\(N=S*2^e.(其中S为>1奇数,e>0)\)

构造法(构造出满足一个条件的情况,判断是否满足另一个条件)+分析法证明存在性

\(存在i,j<=N,满足(x-y)*(x+y+1)==0(mod N).\)

\(使上式满足条件,令x-y=S,x+y+1=2^(e+1)\)

\(解得x=1/2*(2^(e+1)-1+S),y=1/2*(2^(e+1)-1-S);\)

\(是否保证i,j<=N?\)

\(证明1/2*(2^(e+1)+1+S)<=S*2^e\)

\(即证2^(e+1)-1+S<=2^ (e+1)*S\)

\(即证2^(e+1)>=1\)

得证.

故此时无法构成N的完全剩余系.

POJ3244 Difference between Triplets

POJ3910

\(对于一个封闭集合S = {x1, x2, ..., xn},xi的因数d均在集合中,则有下面行列式的值: \)

\(=(1<=i<=n)φ(xi) \)

Category: 树套树 | Tags: | Read Count: 92

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com