首页 > 代码库 > HDU5072 Coprime (乱搞?)
HDU5072 Coprime (乱搞?)
题目链接 ： http://acm.hdu.edu.cn/showproblem.php?pid=5072
求n个不同的数(<=1e5)中有多少组三元组(a, b, c)两两不互质或者两两互质。
做法：
假定a < b < c
(x, y, z)表示a和b之间的关系是X,a和c之间是Y,b和c之间关系是Z，X,Y,Z∈{0， 1}, 这里0代表不互质，1代表互质
考虑到正的来做有点难，可以反的来做这题，总共(a,b,c)之间有8种关系
我们可以求出其它6种，然后减一下就行了。
先排序。
A = {在b前与c互质的数量 * 在c前与c不互质的数量} + {在c后与c互质的数量 * 在c后与c不互质的数量}；
B = {在b前与b互质的数量 * 在b后与b互质的数量} + {在b前与b不互质的数量 * 在b后与b不互质的数量};
Sum = 总共有多少组三元组;
那么其实我们所求的答案就是(B - A + Sum) / 2 ; 这个建议自己推一下，也不是很复杂
至于求在c前与c互质OR不互质的数量的话可以用容次搞搞，复杂度是可以过的。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 6 using namespace std; 7 typedef __int64 lld; 8 const int MAXN = 100005; 9 10 int a[MAXN];11 int cnt[MAXN];12 vector<int> prime[MAXN];13 int check[MAXN] = {0};14 int n;15 lld ans[MAXN][2];16 17 int calc(vector<int> arr) {18 int m = arr.size();19 int sum = 0;20 for (int i = 1; i < (1 << m); i++) {21 int fg = -1, ret = 1;22 for (int j = 0; j < m; j++) {23 if (i >> j & 1) {24 ret *= arr[j]; fg = -fg;25 }26 }27 sum = sum + fg * cnt[ret];28 cnt[ret] += 1;29 }30 return sum;31 }32 33 void work() {34 scanf("%d", &n);35 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);36 sort(a + 1, a + 1 + n);37 memset(cnt, 0, sizeof(cnt));38 for (int i = 1; i <= n; i++) {39 ans[i][0] = calc(prime[a[i]]);40 }41 memset(cnt, 0, sizeof(cnt));42 for (int i = n; i >= 1; i--) {43 ans[i][1] = calc(prime[a[i]]);44 }45 lld Sum = (lld)n * (n-1) * (n-2) / 6;46 lld A = 0;47 lld B = 0;48 for (int i = 1; i <= n; i++) {49 A += ans[i][0] * (i-1 - ans[i][0]);50 A += ans[i][1] * (n-i - ans[i][1]);51 B += ans[i][0] * ans[i][1];52 B += (i-1 - ans[i][0]) * (n-i - ans[i][1]);53 }54 printf("%I64d\n", B-A+Sum >> 1);55 return ;56 }57 58 int main() {59 for (int i = 2; i <= 1e5; i++) {60 if (!check[i]) {61 for (int j = 1; j * i <= 1e5; j++) {62 check[j * i] = 1;63 prime[j*i].push_back(i);64 }65 }66 }67 int T;68 scanf("%d", &T);69 for (int cas = 1; cas <= T; cas++) work();70 return 0;71 }
HDU5072 Coprime (乱搞?)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。