Coprime
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 400 Accepted Submission(s): 178
Now the Ragnarok is coming. We should choose 3 people to defend the evil. As a group, the 3 people should be able to communicate. They are able to communicate if and only if their id numbers are pairwise coprime or pairwise not coprime. In other words, if their id numbers are a, b, c, then they can communicate if and only if [(a, b) = (b, c) = (a, c) = 1] or [(a, b) ≠ 1 and (a, c) ≠ 1 and (b, c) ≠ 1], where (x, y) denotes the greatest common divisor of x and y.
We want to know how many 3-people-groups can be chosen from the n people.
For each test case, the first line contains an integer n(3 ≤ n ≤ 105), denoting the number of people. The next line contains n distinct integers a1, a2, . . . , an(1 ≤ ai ≤ 105) separated by a single space, where ai stands for the id number of the i-th person.
题意:
给出 T 组样例,每组样例都有个 N,代表有 N 个数,问能有多少种 3 元组组合,使其 3 个任意两者之间互质或者不互质。
思路:
容斥定理 + 筛选。问题的逆命题就是,三者之间的组合存在的关系的:互质,互质,不互质;不互质,不互质,互质。而对于一个数来说,互质 + 不互质 + 1 = n,所以转换为求一个数互质与不互质的个数分别是多少。且通过求互质的数,就可以得出不互质的数是多少。得出这样的结论之后,问题又转化成了求一个数互质的数共有几个。
首先通过筛选的方法,求出每个因子所构成的数在数列中一共有几个,用 ans 数组保存。之后在统计一个数与之互质的总个数时,也可以运用容斥定理求出。
比如 30 的质因子是 2,3,5,那么所求的总数就是 ans [ 2 ] + ans [ 3 ] + ans [ 5 ] - ans [ 2 * 3 ] - ans [ 2 * 5 ] - ans [ 3 * 5 ] + ans [ 2 * 3 * 5 ](如果质因子个数为 n 个,可发现,当为偶数个质因子构成的合数时,总数需要减,而当为奇数时,则需要加,其实就是容斥定理)。
每个数都这样求出来之后加和后,总数还要 / 2,因为一个数被同时算了两次,最后用 C ( n, 3 ) - res 即为所求。记得用 long long 即可。
求每个因子所构成的数在数列中的个数要用筛选的方法,不然会 TLE。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 100005; int n; int num[N], ans[N], pri[N]; bool vis[N]; void init () { memset(ans, 0, sizeof(ans)); memset(vis, 0, sizeof(vis)); } bool test (int x) { if (x == 1) return false; for (int i = 2; i * i <= x; ++i) { if (!(x % i)) return false; } return true; } ll solve () { ll res = 0; for (int i = 0; i < n; ++i) { int now = num[i], sat = 0, sum = 0; int m = 2; while (m * m <= now) { if (!(now % m)) { pri[sum++] = m; while (!(now % m)) now /= m; } ++m; } if (test(now)) pri[sum++] = now; for (int j = 1; j < (1 << sum); ++j) { int sum1 = 0, temp = 1; for (int k = 0; k < sum; ++k) { if ((1 << k) & j) { ++sum1; temp *= pri[k]; } } if (sum1 & 1) sat += ans[temp]; else sat -= ans[temp]; } if (!sat) continue; res += (ll)(sat - 1) * ((ll)n - sat); } return res / 2; } int main () { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); init(); for (int i = 0; i < n; ++i) { scanf("%d", &num[i]); vis[ num[i] ] = 1; } for (int i = 2; i < N; ++i) { for (int j = i; j < N; j += i) { if (vis[j]) ++ans[i]; } } ll res = (ll)n * (n - 1) * (n - 2) / 6; printf("%I64d\n", res - solve()); } return 0; }
相关推荐
sparse coprime array direction of arrival
Wideband Spectrum SensingBased on Coprime Sampling
判断输入的数字是否质数,再判断这两个数是否互质
Correlation imaging is attracting more and more ... We propose a coprime-frequencied sinusoidal modulation method for speckle pattern creation using a spatial light modulator in a computational ghost
利用MATLAB实现了基于互质阵的DOA估计,相比于传统的DOA算法,基于互质阵的DOA估计能够实现自由度的扩展,提高分辨能力
互质阵MUSIC法,能够有峰值,还有复杂度分析,曲线对比等
编码很简单-一个简单的“ N mod coprime”。) 给定一个大小为M的数据块,中国喷泉可以为您提供几乎无限个大小为N的数据包。 “几乎无限”就是小于或等于2 ^ S的互素数的数量,其中S是位的切片大小。 对于32位片来...
Passivity-based robust control for nonlinear feedback systems using robust right coprime factorization
A Low-computation compressive wideband spectrum sensing algorithm based on multirate coprime sampling
Robust control for uncertain nonlinear system using isomorphism-based robust right coprime factorization
matlab多径信道代码到达方向 DoA 估计代码 2021 年 1 月 17 日 威尔·霍华德 ...包含四个“运行类型”:'single'、'snr_sweep'、'block_sweep'、'ml_gen' ...使用给定参数运行单个试验(见下节),并显示时间平滑与不平滑...
Mathematics for programmers (early draft)Dennis Yurichev <math@yurichev.com>September 22, 20202Contents1 Prime numbers 1 1.1 Integer ... 41.2 Coprime numbers . . . . . . . . . . . . . . . . .
使用Magma编写.//S=[a,b,c],三个数分别由a,b,c个随机数之积构成,GCD=1(互素)的概率。S的长度大于2即可。
欧拉公式求圆周率的matlab代码 Algorithm Note When b is huge, and a and c are coprime, Euler's theorem applies: a^b≡a^bmodϕ(c) mod c
The two number of lines in space of overlapping pairs are made coprime to minimize the number of common blind spots. The third non-overlapping pair is arranged with the space less than the quotient ...