526互联

调和级数枚举倍数模型

发布时间 2023-11-27 22:28:12作者: value0

调和级数枚举倍数模型

参考博客：

算法学习笔记27：素数筛法【埃氏筛法、线性筛法】

OI&ACM]调和级数枚举倍数模型

板子(时间复杂度\(O(nlogn)\))：
for(int i = 1;i<=n;i++)
{
    for(int j = i;j<=n;j += i)
    {
        ???
	}
}
应用：

目前较常见的用处：

\(f[i]:最大公因数为i的倍数的数对数量\)

通过容斥得到：

\(f[i]:最大公因数恰好为i的数对数量\).

for(int i = mx;i;i--)
{
    for(int j = 2 * i;j <= mx;j += i)
    {
        f[i] -= f[j];
	}
}

CF1034A

解题思路：

我们通过\(a\)数组构造\(b\)数组，\(d = gcd(a),b[i] = \frac{a[i]}{d}\)。

根据题目要求，我们要删掉最少的\(b[i]\)，使得剩下的\(b\)的最大公因数大于\(1\)。等价于我们保留最多的\(b[i]\)达到该效果。

我们记录有多少个\(b[i]\)是质数\(x\)的倍数\(cnt[x]\),取最大的\(cnt[x]\)作为保留元素的数量。

答案就是\(n - max(cnt[x])\)。当然，若\(max(cnt[x]) = 0\)，无解。

注意：本题值域很大，之所以用质数筛是为了降低时间复杂度，直接用\(2\sim max(a)\)的遍历筛也能保证正确性。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 998244353;
const int N = 1.5e7 + 10;
int primes[N / 10];
int cnt;
bool st[N];
int num[N];
void sieve(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            st[i] = true;
            primes[cnt++] = i;
        }
        for (int j = 0; i <= n / primes[j]; j++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int mx = 0;
    int d = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        d = gcd(d, a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] /= d;
        mx = max(mx, a[i]);
        num[a[i]]++;
    }
    int ans = 0;
    for (int i = 0; i < cnt; i++)
    {
        int p = primes[i];
        if (p > mx)
        {
            break;
        }
        for (int j = 2 * p; j <= mx; j += p)
        {
            num[p] += num[j];
        }
        ans = max(ans, num[p]);
    }
    if (ans == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << n - ans << endl;
    }
}

int main()
{
    int t = 1;
    // cin >> t;
    sieve(N - 5);
    while (t--)
    {
        solve();
    }
    return 0;
}

CF1877D题Effects of Anti Pimples

解题思路：

先得到\(f[i]:i的倍数下标元素中的最大值。\)

然后排个序，升序遍历，$ans += f[i] * 2^{i - 1} \(。即，对于前面小于等于自身的\)(i - 1)$个数可选可不选。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 998244353;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = 0;
        for (int j = i; j <= n; j += i)
        {
            f[i] = max(f[i], a[j]);
        }
    }
    sort(f.begin() + 1, f.end());
    ll q = 1;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + q * f[i]) % mod;
        q = q * 2 % mod;
    }
    cout << ans << endl;
}

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

CF803F题Coprime Subsequences

解题思路：

题目要求找到最大公因数为1的子序列的个数。

\(cnt[i]:数组中i的倍数出现的次数\)。

\(f[i]:最大公因数为i的倍数的数对数量\)

\(ans[i]:最大公因数恰好为i的数对数\)

\(ans[i] = f[i] - ans[2 * i] - ans[3*i] - ...-ans[k*i],((k + 1) * i >maxval)\)

\(f[i] = 2^{cnt[i]} - 1\)，即数组中\(i\)的倍数出现的元素个数，选或者不选，不能为空。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<ll> q(n + 1);
    q[0] = 1;
    int mx = 0;
    vector<int> cnt(1e6 + 10, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        q[i] = (2 * q[i - 1]) % mod;
        mx = max(mx, a[i]);
        cnt[a[i]]++;
    }
    vector<ll> f(mx + 5), ans(mx + 5);
    // cnt[i]:a数组中a[i]为i的倍数的元素有多少个
    for (int i = 1; i <= mx; i++)
    {
        for (int j = 2 * i; j <= mx; j += i)
        {
            cnt[i] += cnt[j];
        }
    }
    // f[i]:最大公因数为i的倍数的子序列有多少个
    // ans[i]:最大公因数恰好为i的子序列有多少个
    // ans[i] = f[i] - ans[2 * i] - ans[3 * i] - ... - ans[k * i],((k + 1) * i > mx)
    for (int i = mx; i; i--)
    {
        f[i] = q[cnt[i]] - 1;
        ans[i] = f[i];
        for (int j = 2 * i; j <= mx; j += i)
        {
            ans[i] = (ans[i] - ans[j]) % mod;
        }
    }
    ans[1] = (ans[1] + mod) % mod;
    cout << ans[1];
}

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

CF1884D题Counting Rhyme

解题思路：

\(cnt[i]:数组中i的倍数出现的次数\)。

\(f[i]:最大公因数为i的倍数的数对数量\)

\(ans[i]:最大公因数恰好为i的数对数\)

得到\(ans[i]\)后，我们遍历整个值域区间，同样用枚举倍数的方法，判断\(i\)的因子是否在数组\(a\)中出现过。

将没有出现过的\(ans[i]\)数对数量加入答案。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1), cnt(n + 1), e(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
        e[a[i]] = true;
    }
    vector<ll> f(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2 * i; j <= n; j += i)
        {
            cnt[i] += cnt[j];
        }
    }
    for (int i = n; i > 0; i--)
    {
        f[i] = (cnt[i] * (cnt[i] - 1)) / 2;
        for (int j = 2 * i; j <= n; j += i)
        {
            f[i] -= f[j];
        }
    }
    vector<bool> st(n + 1, true);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            if (e[i])
            {
                st[j] = false;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (st[i])
        {
            ans += f[i];
        }
    }
    cout << ans << endl;
}

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

CF1900D - Small GCD

解题思路:

根据式子，不难看出就是遍历三元组全集，所以顺序无关，直接排序同样遍历三元组全集即可。

对排序后的数组取三元组\((a[i],a[j],a[k]),(i < j <k)\)，所以\(a[i] \leq a[j] \leq a[k]\)。那么\((a[i],a[j])\)能够做出贡献的次数为\(n - j\)。

如上，按升序遍历每个元素的因子，记录\(f[i]\)。

\(f[i]:最大公因数为i的倍数的数对数量\)。

\(c[x]:为枚举到当前，所有元素中因子x出现的次数\).由于\(c[x]\)的系数随着遍历位置而改变，所以我们边累计\(f[x]\)边更新\(c[x]\)。

\(f[x] = \sum_{i = 1}^{n}(c_i[x] * (n - i))\)。

然后，经典容斥更新\(f[i]\)得到新\(f[i]\)。

\(f[i]:最大公因数恰好为i的数对数量\).

设\(ans[i]:最大公因数恰好为i的数对数量\)。\(maxval 为值域最大值\)。

\(ans[i] = f[i] - ans[2 * i] - ans[3 * i] - ... -ans[k * i],((k + 1) * i > maxval)\)。

最终答案为\(\sum_{i= 1}^{maxval}(f[i] *i)\)

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
vector<int> b[N];
void solve()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    vector<ll> c(1e5 + 10);
    // 枚举每个a[i]的因子,计算最大公因数为x的倍数的数对数量
    // f[i]:最大公因数为i的倍数的数对数量
    vector<ll> f(1e5 + 10, 0);
    for (int i = 1; i <= n; i++)
    {
        for (auto x : b[a[i]])
        {
            // 此处a[i]为三元组中第二大的数，数组经过排序
            //  所以能组成的合法三元组为(n - i)个
            f[x] += c[x] * (n - i);
            // 边计数边累加
            c[x]++;
        }
    }

    // 经典容斥求得 f[i] : 最大公因数恰好为i的数对数量
    ll ans = 0;
    for (int i = 1e5; i; i--)
    {
        for (int j = i * 2; j <= 1e5; j += i)
        {
            f[i] -= f[j];
        }
        // 每个数对的贡献值就是i
        ans += f[i] * i;
    }
    // cout << 1 << endl;
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    // 筛出j的所有因子
    for (int i = 1; i <= N - 5; i++)
    {
        for (int j = i; j <= N - 5; j += i)
        {
            b[j].push_back(i);
        }
    }
    // cout << 1 << endl;
    while (t--)
    {
        solve();
    }
    return 0;
}