“亚信科技杯”南邮第七届大学生程序设计竞赛之网络预赛 G Prime [ 容斥原理 + 数论 + 求约数 + 素数筛 ]

“亚信科技杯”南邮第七届大学生程序设计竞赛之网络预赛

传送门

Prime

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 234 测试通过 : 5

题目描述

给定n个数,求两两互斥的对数。互斥是指两个数的最大公约数是1

输入

第一行为样例数T(T<=5)

对每个样例，第一行为一个整数n(2=<n<=10^5),代表数的个数。

接下来一行包含n个数，a1,a2,…,an(1<=ai<=10^5)

输出

对于每个样例，在一行输出答案。

样例输入

1
2
2 3

样例输出

题目来源

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
所以答案是1

tag : 容斥原理 + 数论 + 求约数 + 素数筛

题解在继续：

注意点1：

对于n个数，窝们分别分解质因数，枚举约数(约数仅为质数的一次幂构成) ，一开始没注意这个，wa成狗。

注意点2：

会爆int,需要long long

注意点3：

要快速的判断出，一个数仅为质数的一次幂构成，一开始对每个数都进行了扫质数，TLE的好惨。

最后，参照了天猫的方法。

素数筛的时候，顺便记录该数的最大素因子（如果本身是素数，记录0）

再扫一遍，cnt[i]=0表示该数并不是仅为质数的一次幂构成，cnt[i]=1表示在容斥时应该加上num[i]，cnt[i]=-1表示在容斥时应该减去num[i]。

 1 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     }

njczy2010	2079	Accepted	421MS	2556K	1855Byte	G++	2015-04-01 16:08:21.0

njczy2010	2079	Accepted	421MS	2556K	1855Byte	G++	2015-04-01 16:08:21.0
njczy2010	2079	Time Limit Exceed at Test 1			3464Byte	G++	2015-04-01 13:21:17.0
njczy2010	2079	Time Limit Exceed at Test 1			3184Byte	G++	2015-04-01 12:55:05.0
njczy2010	2079	Time Limit Exceed at Test 1			3154Byte	G++	2015-04-01 12:53:21.0
njczy2010	2079	Time Limit Exceed at Test 1			3084Byte	G++	2015-04-01 12:49:09.0
njczy2010	2079	Wrong Answer at Test 1			2966Byte	G++	2015-04-01 12:26:11.0
njczy2010	2079	Wrong Answer at Test 1			2971Byte	G++	2015-04-01 12:25:07.0
njczy2010	2079	Wrong Answer at Test 1			2780Byte	G++	2015-03-31 20:32:44.0
njczy2010	2079	Wrong Answer at Test 1			2694Byte	G++	2015-03-31 20:31:19.0
njczy2010	2079	Wrong Answer at Test 1			2693Byte	G++	2015-03-31 20:27:55.0
njczy2010	2079	Runtime Error at Test 1			2570Byte	G++	2015-03-31 20:26:52.0

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <stack>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <map>
  7 #include <string>
  8 #include <queue>
  9 #include <cmath>
 10 
 11 #define ll long long
 12 int const N = 100005;
 13 int const M = 100005;
 14 int const inf = 1000000000;
 15 ll const mod = 1000000007;
 16 
 17 using namespace std;
 18 
 19 int T;
 20 ll ans;
 21 int f[N];
 22 ll cnt[N];
 23 ll num[N];
 24 int m=N-5;;
 25 int a[N];
 26 int n;
 27 
 28 void pre()
 29 {
 30     int i,j;
 31     int en;
 32     int te;
 33     memset(f,0,sizeof(f));
 34     f[0]=f[1]=1;
 35     for(i=2;i<=m;i++){
 36         if(f[i]==0){
 37             en=m/i;
 38             for(j=i;j<=en;j++){
 39                 f[ j*i ]=i;
 40             }
 41         }
 42     }
 43     memset(cnt,0,sizeof(cnt));
 44     cnt[1]=1;
 45     for(i=2;i<=m;i++){
 46         if(f[i]==0){
 47             cnt[i]=-1;
 48         }
 49         else{
 50             te=i/f[i];
 51             if(te%f[i]==0){
 52                 cnt[i]=0;
 53             }
 54             else{
 55                 cnt[i]=cnt[te]*(-1);
 56             }
 57         }
 58     }
 59 }
 60 
 61 void cal_divisor(int x)
 62 {
 63     int i;
 64     for(i=1;i*i<=x;i++){
 65         if(x%i==0){
 66             num[i]++;num[x/i]++;
 67         }
 68         if(i*i==x){
 69             num[i]--;
 70         }
 71     }
 72 }
 73 
 74 void ini()
 75 {
 76     int i;
 77     ans=0;
 78     memset(num,0,sizeof(num));
 79     scanf("%d",&n);
 80     for(i=1;i<=n;i++){
 81         scanf("%d",&a[i]);
 82         cal_divisor(a[i]);
 83     }
 84 }
 85 
 86 void solve()
 87 {
 88     int i;
 89     for(i=1;i<=m;i++){
 90         if(cnt[i]!=0)
 91             ans+=cnt[i]*num[i]*(num[i]-1)/2;
 92     }
 93 }
 94 
 95 void out()
 96 {
 97     printf("%I64d
",ans);
 98 }
 99 
100 int main()
101 {
102     pre();
103     //freopen("data.in","r",stdin);
104     //freopen("data.out","w",stdout);
105     scanf("%d",&T);
106     //for(int cnt=1;cnt<=T;cnt++)
107     while(T--)
108     //while(scanf("%d%d%d",&a,&b,&n)!=EOF)
109     {
110         ini();
111         solve();
112         out();
113     }
114 }