[CF547C] Mike and Foam

[CF547C] Mike and Foam - 组合,容斥,数论

Description

给一些数，每次操作将某个数激活或者禁用，输出当前所有激活的数中互质的数对的个数。数大小不超过 (5 imes 10^5)

Solution

一个数的不同的质因子最多有 7 个

显然求互质是不大方便的，我们考虑转化为非互质，即有公共的质因子

现在考虑一个数上架的情况，所有与他有公共质因子的数都会产生一次贡献

所以我们容斥着统计就可以了

具体地，我们需要维护一个 (cnt[i]) 表示当前有多少个激活的数以 i 为因子，计算时枚举每个因子是否选择，然后容斥统计答案即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1000005;
int n, q, a[N], b[N], cnt[N], ans = 0, tot = 0;
vector<int> fac[N], allfac[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int t = a[i];
        for (int j = 2; j * j <= a[i]; j++)
        {
            if (t % j == 0)
            {
                while (t % j == 0)
                    t /= j;
                fac[i].push_back(j);
            }
        }
        if (t > 1)
            fac[i].push_back(t);
        }
    for (int i = 1; i <= q; i++)
    {
        int id;
        cin >> id;
        if (b[id] == 0)
        {
            b[id] = 1;
            int siz = fac[id].size();
            for (int s = 0; s < 1 << siz; s++)
            {
                int sign = __builtin_popcount(s) % 2 ? 1 : -1;
                int num = 1;
                for (int j = 0; j < siz; j++)
                    if (s & (1 << j))
                        num *= fac[id][j];
                ans += cnt[num] * sign;
            }
            for (int s = 1; s < 1 << siz; s++)
            {
                int num = 1;
                for (int j = 0; j < siz; j++)
                    if (s & (1 << j))
                        num *= fac[id][j];
                cnt[num]++;
            }
            ++tot;
        }
        else
        {
            b[id] = 0;
            int siz = fac[id].size();
            for (int s = 1; s < 1 << siz; s++)
            {
                int num = 1;
                for (int j = 0; j < siz; j++)
                    if (s & (1 << j))
                        num *= fac[id][j];
                cnt[num]--;
            }
            for (int s = 0; s < 1 << siz; s++)
            {
                int sign = __builtin_popcount(s) % 2 ? 1 : -1;
                int num = 1;
                for (int j = 0; j < siz; j++)
                    if (s & (1 << j))
                        num *= fac[id][j];
                ans -= cnt[num] * sign;
            }
            --tot;
        }
        cout << tot * (tot - 1) / 2 - ans << endl;
    }
}