[SPOJ NO GCD]

发表于 | 更新于 | 分类于 ，
本文字数： 15k

链接

\(\text{SPOJ - NO GCD}\)

题意

  给你一个长度为\(n\)的序列\(a\)，并且对于任意一个数\(a[i]\)，它只有小于\(50\)的素因子，且不含有平方因子，求有多少对\((i,j)\)，使得\(a[i]和a[j]\)互质，或者\(gcd\)是质数。

  输入格式：第一行输入\(t\)，包含\(t\)组样例，下面每组样例第一行一个\(n\)，下面一行输入一个长度为\(n\)的序列\(a\)。

  数据范围：\(1\leq t\leq 10,1\leq 100000\).

  输出格式：每个样例对应一行一个输出结果。

分析

  这一题是偶然在别人博客看到的，几乎没怎么写过数学题，感到这个思路非常非常的巧妙。

  首先考虑到了\(50\)以内的素数仅有\(15\)个，而对于\(a\)序列中的任意两个数来说，它们的\(gcd\)要么为\(1\)，要么在这\(15\)个素数之中，要么为\(1\)，如果用二进制表示，那么则有它们二进制表示的与的结果为\(0\)，或者某一位为\(1\)(恰好有一个素因子)。对于一个二进制表示\(i\)来说，我们需要求出它的个数与，它补集的子集个数的乘积，这即是求出了\(gcd\)为\(1\)的情况，对于不为\(1\)的情况，我们求出它与，它的补集对某一位\(0\)取反变成\(1\)的所有子集个数在减去它补集没去反之间子集的个数，这二者乘积，对所有的状态进行累加。

  关键是如何快速求子集个数，对于\(i\)，求所有的\(j\)，\(j\leq i \&\&(i|j)==i\)。网上代码为：

1
2
3
4
5
6
7
for(i=0;i<M;i++){
    for(j=i;;j=(j-1)&i){   
	//s[i]为i的子集的个数，子集j对应的个数为num[j]     
        s[i]+=num[j]; //关键，得到子集 
        if(!j) break;
    }
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define MOD 1000000007
#define P 2


typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

const int M = 1 << 15;

int t, n, a[M], b[M], p[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
                                //2,3,5,7,11,13,17,19,23,29,31,37,41,43,47
int main() {
    cin >> t;
    while (t--) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        cin >> n;
        ll x;
        for (int i = 1; i <= n; i++) {
            cin >> x;
            int temp = 0;
            for (int j = 0; j < 15; j++)
                if (x % p[j] == 0) temp += (1 << j);
            //x为1时，temp为0
            a[temp]++;
        }
        for (int i = 0; i < M; i++)
            //枚举j二进制表示下的子集
            for (int j = i;;j = (j - 1)& i) {
                b[i] += a[j];
                //写在这里，是考虑特殊情况，比如输入的x为1
                if (!j) break;
            }
        ll ans = 0;
        for (int i = 0; i < M; i++) {
            //gcd为1
            ans += 1ll * a[i] * b[i ^ (M - 1)];
            //gcd为一个素数
            for (int j = 0; j < 15; j++)
                if ((i >> j) & 1)
                    ans += 1ll * a[i] * (b[i ^ (M - 1) ^ (1 << j)] - b[i ^ (M - 1)]);
        }
        cout << ans << endl;
    }
}