组合数学的问题
先引入一个简单问题假如问1-100内至少能被2,3,5之一整除的数的个数
答案应为1-100中2的倍数+3的倍数+5的倍数-2,3的公倍数-2,5的公倍数-3,5的公倍数+2,3,5的公倍数(以上全代表个数)
由次推广开来对任意此类问题则有{C(n,1)}-{C(n,2)}+{C(n,3)}...+(-1)^(n-1){C(n,n)}其中{C(n,i)}代表n中选i个数的组合在给定范围内能被选出的i个数的最小公倍数整除的数的个数
有了以上铺垫下面的问题就好解决了
(1)上面问题4个数的推广注意3是9的约数求最小公倍数时候不要简单相乘
answer=[2000/2]+[2000/3]+[2000/5]+[2000/9]-[2000/2/3]-[2000/2/5]-[2000/2/9]-[2000/3/5]-[2000/9]-[2000/5/9]+[2000/2/3/5]+[2000/2/9]+[2000/2/5/9]+[2000/5/9]-[2000/2/5/9]=1466
其中[x]表示x的取整数部分的高斯函数例如[3.3333]=3,[2000/6]=333
(2)至少被2个同时整除可先求出4个数中任意2个的最小公倍数然后重复上面步骤即可最小公倍数应为6101518945共6个数
最终结果为446
呼Allbymyself应该讲的够明白了