调和级数枚举倍数模型
参考博客：
算法学习笔记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;
}