“亚信科技杯”南邮第七届大学生程序设计竞赛之网络预赛
G:
Prime
题目描述
给定n个数,求两两互斥的对数。互斥是指两个数的最大公约数是1
输入
第一行为样例数T(T<=5)
对每个样例，第一行为一个整数n(2=<n<=10^5),代表数的个数。
接下来一行包含n个数，a1,a2,…,an(1<=ai<=10^5)
输出
对于每个样例，在一行输出答案。
样例输入
122 3
样例输出
1
题目来源
NUPT
先转一发kss的题解：
思路：对于n个数，窝们分别分解质因数，枚举约数(约数仅为质数的一次幂构成)，比如20，有约数2 5 10.用一个num数组统计这些约数出现的个数。接下来枚举n个数，对于第i个数，窝们枚举它的所有约数，用cnt记录这个约数是由几个质数相乘得到的。不妨设此时约数为j，那么如果cnt是奇数，那么ans[i]+=num[j]，不然ans[i]-=num[j]。最后统计出来的ans为与第i个数不互质的个数，所以n-ans[i]表示与第i个数互质的个数.即为所求。
1.其实，简略来说，就是对于每个数 a[i]，去求与a[i]不互质的数的个数ans（包括了a[i]），然后与a[i]互质的数的个数就是 n-ans。
2.与a[i]不互质等价于 与a[i]有除了1以外的共同约数。所以，我们对每个数a[i]求所有约数，然后进行累加（如 12 ，有约数 2 3 4 6 12 ，则num[2]++,num[3]++ ....），把每个数都如此处理。
3.对于求与a[i]不互质的数的个数ans，需要用到容斥原理， 与a[i]有共同约数的数的个数（ans）= 与a[i]有1个约数相同的数的个数 - 与a[i]有2个约数相同的数的个数 + 与a[i]有3个约数相同的数的个数...
对容斥原理不太了解的可参见：
第三条就是对kss题解： 不妨设此时约数为j，那么如果cnt是奇数，那么ans[i]+=num[j]，不然ans[i]-=num[j]。 的解释。
4.求1-n的所有素数可以用素数筛法，求解一个数所有的约数可以从2-sqrt(a) 枚举。
再举个栗子：
N=3
2 5 10
那么num[2]=2，num[5]=2，num[10]=1 那么对于2，ans=num[2]=2, n-ans=1同理5也是1
对于10，ans=num[2]+num[5]-num[10]=2+2-1=3 n-ans= 0 全加起来为2然后/2
所以答案是11 memset(cnt,0,sizeof(cnt)); 2 cnt[1]=1; 3 for(i=2;i<=m;i++){ 4 if(f[i]==0){ 5 cnt[i]=-1; 6 } 7 else{ 8 te=i/f[i]; 9 if(te%f[i]==0){10 cnt[i]=0;11 }12 else{13 cnt[i]=cnt[te]*(-1);14 }15 }16 }
| | | Accepted | 421MS | 2556K | 1855Byte | | 2015-04-01 16:08:21.0 |
| | | Accepted | 421MS | 2556K | 1855Byte | | 2015-04-01 16:08:21.0 |
| | | Time Limit Exceed at Test 1 | 3464Byte | | 2015-04-01 13:21:17.0 | ||
| | | Time Limit Exceed at Test 1 | 3184Byte | | 2015-04-01 12:55:05.0 | ||
| | | Time Limit Exceed at Test 1 | 3154Byte | | 2015-04-01 12:53:21.0 | ||
| | | Time Limit Exceed at Test 1 | 3084Byte | | 2015-04-01 12:49:09.0 | ||
| | | Wrong Answer at Test 1 | 2966Byte | | 2015-04-01 12:26:11.0 | ||
| | | Wrong Answer at Test 1 | 2971Byte | | 2015-04-01 12:25:07.0 | ||
| | | Wrong Answer at Test 1 | 2780Byte | | 2015-03-31 20:32:44.0 | ||
| | | Wrong Answer at Test 1 | 2694Byte | | 2015-03-31 20:31:19.0 | ||
| | | Wrong Answer at Test 1 | 2693Byte | | 2015-03-31 20:27:55.0 | ||
| | | Runtime Error at Test 1 | 2570Byte | | 2015-03-31 20:26:52.0 |
1 #include2 #include 3 #include 4 #include 5 #include 6 #include