11的倍数c语言 11-1 5 11 12的倍数(容斥原理)

容斥原理的描述如下：

要计算几个集合并集的大小，我们要先将单个集合的大小计算出来，然后减去两个集合相交的部分，再加回三个集合相交的部分，再减去四个集合相交的部分，以此类推，一直计算到所有集合相交的部分。

所以这个题目要求的是不是2 5 11 13的倍数，可以求是2 5 11 13的倍数之后，再减去即可。

这样就会用到容斥原理，先求仅仅只是整除2, 5 , 11, 13的数量，再减去整除了它们之间两两的乘积的数量，再加上整除它们三个之间的乘积的数量，再加上整除四个的数量。

而这个数量也很有意思，1到num中整除c的数量正是num/c的值: 例如1,2，p,..2p, ..3p...4p..xp..n;易知1到n中能整除p的都是P的倍数，即为1倍,2倍等等，所以符合要求的倍数个数为x个，有xp <= n 所以 x = n / p (取整).

#include

#include

#include

using namespace std;

typedef long long ll;

int main()

{

ll n,t;

while(scanf("%lld", &n) != EOF){

t=0;

t += n / 2;

t += n / 5;

t += n / 11;

t += n / 13;

t -= n / 2 / 5;

t -= n / 2 / 11;

t -= n / 2 / 13;

t -= n / 5 / 11;

t -= n / 5 / 13;

t -= n / 11 / 13;

t += n / 2 / 5 / 11;

t += n / 2 / 5 / 13;

t += n / 2 / 11 / 13;

t += n / 11 / 5 / 13;

t -= n / 2 / 5 / 11 / 13;

printf("%lld\n", n - t);

}

return 0;

}