- 数论题已知正整数a,b,..,k,l,求在1,2,...,n中与
- 已知正整数a,b,..,k,l,求在1,2,...,n中与已知正整数皆互素的整数的个数。
- Q=a*b*..*k*l,
A={p素数,p|Q且p≤n},m=|A|
S={1,2,...,n},
T(k)={p(k)s,p(k)s≤n且p(k)∈A}
B={u∈S,(u,Q)=1}=
=S-∪{p(k)∈A}T(k)
根据容斥定理得:
|B|=|S|-∑{p(k)∈A}|T(k)|+∑{p(k1),p(k2)∈A}|T(k1)T(k1)|+
+...+(-1)^m}|T(k1)T(k1)...T(km)|
其中|T(k)|=[n/p(k)],|T(k1)T(k1)|=[n/(p(k1)p(k1))],
...
|T(k1)T(k1)...T(km)|=[n/(p(k1)p(k1)..p(km))].
1.
若n的素因子=A,则|B|=n∏{p(k)∈A}(1-1/p(k)).
2.
n=v∏{p(k)∈A}p(k),则|B|=n∏{p(k)∈A}(1-1/p(k)).
3.若n不是∏{p(k)∈A}p(k)的倍数,则不易化简.