题解 CF630K 【Indivisibility】

· · 题解

这道题其实是一道普通的容斥原理

解法

题目是想知道 Petya 能够获得多少次奖励，也就是说让我们把不能被2至10整除的数的个数算出来。然而我们可以发现，2至10只有2,3,5,7这四个数是有效的，因为4能被2整除，6能被3整除，8能被2整除，9能被3整除，10能被5整除，即使除上了，也没有意义，还会添加很多麻烦。

所以我们可以先定义一个数，把它赋值为输入的那个数，然后减去能被2,3,5,7整除的数的个数（一切的数据都开 long long ）

    long long n ;
    cin >> n ;
    long long s = n ;
    s -= n / 2 + n / 3 + n / 5 + n / 7 ;

然后我们会疑惑，为什么算出来是个负数，其实，想到容斥原理我们可以发现（如图），当我们在减去2的倍数的个数和3的倍数的个数时，多减了一次6的倍数的个数，所以我们要加上一次6的倍数的个数。我们可以以此推类，当我们在减去两个数的倍数的个数时，我们则减多了一次他们的最小公倍数的倍数的个数，所以我们要加上一次，就刚好了。

![](

所以我们可以根据2*3=6，2*5=10，2*7=14，3*5=15，3*7=21，5*7=35得到

s += n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35 ;

但是我们又可以发现，输出的数还是不太对，对了，还有三个数一起的最小公倍数的倍数个数没处理（如图），经过思考，我们可以知道，在第一次减去四个数的分别倍数的个数的时候，减去了三次，第二次加上的时候也加上了三次，所以我们要再减一次。

![](

我们可以得到

s -= n / 30 + n / 105 + n / 42 + n / 70 ;

最后我们来处理四个数的最小公倍数210的倍数个数，我们可以得到，在第一次是我们减去了四次，在第二次时我们加上了6次，在第三次时我们又减去了4次，所以一共减去了2次，要使他只减去1次，我们只要加上一次即可。我们可以得到

s += n / 210 ;

一切问题都处理完了，上代码（ c++ ）！

#include<bits/stdc++.h>
using namespace std ;
int main()
{
    long long n ;
    cin >> n ;
    long long s = n ;
    s -= n / 2 + n / 3 + n / 5 + n / 7 ;
    s += n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35 ;
    s -= n / 30 + n / 105 + n / 42 + n / 70 ;
    s += n / 210 ;
    cout << s ;
}

真心希望能帮助到大家！