Coprime Conundrum 容斥原理

https://www.hackerrank.com/contests/hourrank-13/challenges/arthur-and-coprimes

我们可以枚举每一个p在[2, sqrt(n)]里，然后就是在[p + 1, n / p]中找有多少个数和p互质了。

标准容斥，先算出[1, n / p]中有多少个和p互质，这个是不能用欧拉定理做的，需要把p质因数分解，然后dfs

求解元素X在区间[1, up]中，有多少个数和X互质。（容斥）

思路：把X质因数分解，多了的不要。12 = 2 * 3。然后有个明显的道理就是如果是2的倍数的话，那么就一定不会与12互质，所以需要减去2的倍数，减去3的倍数，再加上6的倍数。容斥的思路好想，但是不怎么好写。所以结果是总数量up – 不互质的个数。

预处理；his[val][]表示元素val拥有的质因子，Size[val]表示有多少个。记得1是不做任何处理的。就是Size[1] = 0。Dfs的cur表示下一次从哪里开始，不往回枚举，就是任意k个值。

int calc(int up, int cur, int number, int tobuild, int flag) {  //一开始flag是0。0表示加，1减

    int ans = 0;

    for (int i = cur; i <= Size[number]; ++i) {

        if (flag == 0) {

            ans += up / (his[number][i] * tobuild);

        } else ans -= up / (his[number][i] * tobuild);

        ans += calc(up, i + 1, number, his[number][i] * tobuild, !flag);

    }

    return ans;

}

计算12在[1, 24]就是24 - calc(24, 1, 12, 1, 0)。tobuild是选择k个质因数后生成的数字。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 50000 + 20;
int prime[maxn];
bool check[maxn];
int total;
int Size[maxn];
int his[maxn][50 + 20];
void initprime() {
    for (int i = 2; i <= maxn - 20; i++) {
        if (!check[i]) {
            prime[++total] = i;
        }
        for (int j = 1; j <= total; j++) {
            if (i * prime[j] > maxn - 20) break;
            check[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    for (int i = 1; i <= maxn - 20; ++i) {
        int t = i;
        for (int j = 1; j <= total; ++j) {
            if (prime[j] > t) break;
            if (t % prime[j] == 0) {
                his[i][++Size[i]] = prime[j];
                while (t % prime[j]) {
                    t /= prime[j];
                }
            }
        }
    }
    return ;
}
LL calc(int up, int cur, int number, int tobuild, int flag) {
    LL ans = 0;
    for (int i = cur; i <= Size[number]; ++i) {
        if (flag == 0) {
            ans += up / (his[number][i] * tobuild);
        } else ans -= up / (his[number][i] * tobuild);
        ans += calc(up, i + 1, number, his[number][i] * tobuild, !flag);
    }
    return ans;
}
void work() {
    int n;
    cin >> n;
    int en = (int)sqrt(n + 0.5);
//    cout << en << endl;
    LL ans = 0;
    for (int i = 2; i <= en; ++i) {
        ans += n / i - calc(n / i, 1, i, 1, 0);
        ans -= i - calc(i, 1, i, 1, 0);
//        cout << calc(n / i, 1, i, 1, 0) << "  " << calc(i, 1, i, 1, 0) << endl;
//        cout << ans << endl;
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    initprime();
    work();
    return 0;
}