首页 > 代码库 > hdu 5072 Coprime(数论)
hdu 5072 Coprime(数论)
题目链接:hdu 5072 Coprime
题目大意:给定N个数,问能选出多少个3元组,要么[(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠
1]。
解题思路:这题可以换个角度想,可以将三个数看做三角形的三条边,互质即边的颜色为1,否则为0,那么要求的即为
三条边颜色相同的三角形有多少个。
总的三角形的个数可求,那么如果求出三条边不完全相同的三角形个数,相减一下即可。
枚举顶点,然后确定以该点形成的三角会形成多少个不满足三角形,即在1中选一条,0中选一条。这样的话一个不满足
三角形会被计算2次,ans / 2即可。
那么问题转换成求每个数互质或者不互质的数有多少个,将每个数差分质因子,统计每个包含质因子x的数有多少个,
最用计算每个数的时候,用容斥原理计算即可。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5;
int np, pri[maxn + 5], vis[maxn + 5];
int k, fac[maxn + 5];
int v[maxn + 5];
vector<int> g[maxn + 5];
void prime_table(int n) {
np = 0;
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i * 2; j <= n; j += i)
vis[j] = 1;
}
}
void div_fac(int n, int& cnt) {
cnt = 0;
for (int i = 0; i < np && pri[i] * pri[i] <= n; i++) {
if (n % pri[i] == 0) {
fac[cnt++] = pri[i];
while (n % pri[i] == 0)
n /= pri[i];
}
}
if (n != 1)
fac[cnt++] = n;
}
void dfs (int u, int d, int idx) {
if (d >= v[idx]) {
if (u != 1)
g[idx].push_back(u);
return;
}
dfs(u, d + 1, idx);
dfs(u * fac[d], d + 1, idx);
}
void init () {
np = 0;
memset(vis, 0, sizeof(vis));
prime_table(maxn);
for (int i = 2; i <= maxn; i++) {
div_fac(i, v[i]);
dfs(1, 0, i);
}
}
int N, f[maxn + 5], c[maxn + 5];
void input () {
int x;
scanf("%d", &N);
memset(c, 0, sizeof(c));
memset(f, 0, sizeof(f));
for (int i = 0; i < N; i++) {
scanf("%d", &x);
c[x]++;
}
for (int i = 2; i <= maxn; i++) {
if (c[i] == 0)
continue;
for (int j = 0; j < g[i].size(); j++)
f[g[i][j]] += c[i];
}
}
typedef long long ll;
int count (int n) {
int ret = 0;
for (int i = 0; i < g[n].size(); i++) {
int k = g[n][i];
if (v[k]&1)
ret += (f[k] - 1);
else
ret -= (f[k] - 1);
}
return ret;
}
ll solve () {
ll ret = 0;
for (int i = 2; i <= maxn; i++) {
if (c[i] == 0)
continue;
ll k = count(i);
ret += k * (N - 1 - k);
}
ll a = N;
ll sum = 1LL * a * (a - 1) * (a - 2) / 6;
return sum - ret / 2;
}
int main () {
init();
int cas;
scanf("%d", &cas);
while (cas--) {
input();
printf("%I64d\n", solve());
}
return 0;
}
hdu 5072 Coprime(数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。