526互联

Codeforces Round 904 (Div. 2) D. Counting Rhyme

发布时间 2023-12-03 20:48:32作者: .Ivorelectra

题意：给一个序列。一个pair，不同时被序列中的某个数整除。求有多少个这样的pair。
题解：也就是他们的gcd并不是某一个数的倍数。只需要做一个gcd卷积。。？后缀和 gcd卷积

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int>P;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
const double eps = 1e-11;
const double pi = 3.141592653;

void solve()
{
    int n;
    cin >> n;
    ll ans = 0;
    vector<ll> f(n+1);
    vector<int> g(n+1);
    for(int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        f[a] += 1;
        g[a] = 1;
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 2*i; j <= n; j += i)
        {
            g[j] |= g[i]; //记录是不是有一个数整除它
            f[i] += f[j]; //前缀和
        }
    }
    for(int i = 1; i <= n; ++i) f[i] *= f[i];
    for(int i = n; i; --i)
    {
        for(int j = 2*i; j <= n; j += i)
        {
            f[i] -= f[j];
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!g[i]) ans += f[i];
    }
    ans /= 2; //因为每一个算了两遍
    cout << ans << "\n";
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}