首页 > 代码库 > 2014 ACM Regional hdu 5072
2014 ACM Regional hdu 5072
ACM退役两年了， 没想到今年机缘巧合能去鞍山参加Regional了。 记得第一次参加Regional的时候那个心情很激动，激动的很难描述出来。而这次参加Regional一点压力都木有，感觉比参加省赛都轻松，甚至就像是在做练习赛似的。由于本来水平就不高，又隔了两年，所以毫无悬念地拿了个铜牌。
比赛时候C题基本已经想到了解法，由于时间的原因，没能过掉。
C题现在在hdu的5072题。
题意： 给出n个数（n<100000）, 每个数都不大于100000，数字不会有重复。现在随意抽出3个，问三个彼此互质 或者 三个彼此不互质的数目有多少。
思路： 这道题的原型是同色三角形， 可能现场很多队伍都知道这个模型， 所以这道题当时过的队伍还是挺多的。
这道题反着想，就是三个数中只有一对互质 或者只有两对互质的个数。
研究后发现 对于每个数字求出与其不互质的个数k 那么 sum ( k*(n-1-k) )/2 就是相反的数目， 所以最终的答案就是 C(n,3) - sum ( k*(n-1-k) )/2.
现在依然存在一个问题就是如何求出每个数的不互质数的个数，这个其实用容斥原理。 对于数字 a ，求出a的所有素因子， 然后枚举素因子可以构成的所有数字(构成数的过程中素因子用的个数不能超过1) w，
求出原先数组中能整出w的个数。 如果w的素因子个数为奇数就加， 偶数就减。 这就是容斥的过程。
现在还是存在一个问题， 如何快速算出原先数组中能整出w的个数。 首先对原先数据中的每个数字a， 求出所有的素因子， 然后枚举素因子可以构成的所有数字(构成数的过程中素因子用的个数不能超过1)，
对于每一个枚举的数统计加1. 这样就能提前预处理出来。
算法的整体复杂度为 O(n*64*6);
AC代码：
#include <cstdio>#include <cstring>#include <queue>#include <string>#include <iostream>using namespace std;const int N = 200500;typedef long long LL;int p[N];int num;bool in[N];int a[N];int n;int nn[N];void get_prime(){ num = 0; for(int i=2; i<N; i++) { if(!in[i]) { p[num++] = i; for(int j=i; j<N; j+=i) { in[j] = true; } } }}void init(){ memset(nn, 0, sizeof(nn)); int cnt = 0; int ele[100]; scanf("%d", &n); int temp = 0; for(int i=0; i<n; i++) { scanf("%d", &a[i]); temp = a[i]; cnt = 0; for(int j=0; p[j]*p[j] <= temp; j++) { if(temp % p[j] == 0) { ele[cnt++] = p[j]; while(temp%p[j] == 0) temp /= p[j]; } } if(temp != 1) { ele[cnt++] = temp; } for(int j=1; j<(1<<cnt); j++) { temp = 1; for(int k=0; k<cnt; k++) { if( (1<<k) & j ) { temp *= ele[k]; } } nn[temp]++; } }}void solve(){ LL ans = n; LL ss = 0; int temp; ans = ans*(n-1)*(n-2)/6; for(int i=0; i<n; i++) { int cnt = 0; int ele[100]; temp = a[i]; cnt = 0; for(int j=0; p[j]*p[j] <= temp; j++) { if(temp % p[j] == 0) { ele[cnt++] = p[j]; while(temp%p[j] == 0) temp /= p[j]; } } if(temp != 1) { ele[cnt++] = temp; } LL ret = 0; for(int j=1; j<(1<<cnt); j++) { temp = 1; int hh = 0; for(int k=0; k<cnt; k++) { if( (1<<k) & j ) { temp *= ele[k]; hh++; } } if(hh%2 == 1) ret += nn[temp]; else ret -= nn[temp]; } if(ret == 0) continue; ss = ss + (ret-1)*(n-ret); // cout<<i<<" "<<ret<<" "<<ss<<endl; } cout<<ans - ss/2<<endl;}int main(){ get_prime(); int t; scanf("%d", &t); while(t--) { init(); solve(); } return 0;}
2014 ACM Regional hdu 5072