组合数学的问题
先引入一个简单问题 假如问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个的最小公倍数 然后重复上面步骤即可 最小公倍数应为6 10 15 18 9 45 共6个数
最终结果为446
呼 All by myself 应该讲的够明白了 组合数学的问题
先引入一个简单问题 假如问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个的最小公倍数 然后重复上面步骤即可 最小公倍数应为6 10 15 18 9 45 共6个数
最终结果为446
呼 All by myself 应该讲的够明白了