原题链接:CF1900D,题意不多赘述。
首先可以将 \(a\) 数组排序,并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会。
假设我们当前已经枚举到了 \(a_i\),设 \(f_k\) 表示 \(a_1\) 到 \(a_{i-1}\) 中是 \(k\) 的倍数的数有多少个,\(g_k\) 表示 \(a_{1}\) 到 \(a_{i-1}\) 中满足 \(\gcd(a_j,a_i)=k\) 的数有多少个。\(f_k\) 可以直接通过枚举每一个数的所有因子算出,\(g_k\) 可以考虑用容斥算出。具体的,首先将 \(g_k\) 赋值为 \(f_k\),但是我们会发现有一些数不满足条件。比如 \(4\) 和 \(8\) 都是 \(2\) 的倍数,但是 \(\gcd(4,8) \ne 2\),所以我们直接将每一个 \(g_k\) 都减去 \(g_x(k \mid x,x \mid a_i)\) 即可。对于每一个 \(a_i\),最终答案为 \(\sum g_j\times j \times (n-i)\)。
可以先预处理出 \(1\) 到 \(100000\) 的所有因数,小常数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
int t,n,a[MAXN],f[MAXN],g[MAXN];
vector <int> v[MAXN];
signed main()
{
for(int i = 1e5;i >= 1;i--)
for(int j = i;j <= 1e5;j += i) v[j].emplace_back(i);
cin >> t;
while(t--)
{
memset(f,0,sizeof f),memset(g,0,sizeof g);
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1,a + n + 1);
int ans = 0;
for(int i = 1;i <= n;i++)
{
for(auto j : v[a[i]]) g[j] = f[j],f[j]++;
for(auto j : v[a[i]])
for(auto k : v[j]) if(k != j) g[k] -= g[j];
for(auto j : v[a[i]]) ans += (g[j] * (n - i) * j);
}
cout << ans << endl;
}
return 0;
}
标签:gcd,int,题解,times,枚举,MAXN,Small,CF1900D
From: https://www.cnblogs.com/Creeperl/p/17913380.html