BZOJ 4454: C Language Practice

Description

给定一个长度为n的序列$ a_0, a_1, … , a_{n-1} $ 以及一个长度为m的序列 $ b_0, b_1, … , b_{m-1} $ 求出

$$ \sum_{i=0}^{n-1} \sum_{j=0}^{m-1} \gcd(a_i,b_j) \otimes i \otimes j $$

因为答案可能很大，你只需要数出答案对$2^{32}$ 取模的结果即可

$\gcd(0,0)=0$

Input

第一行输入一个正整数T(T<=85)，表示测试数据的组数。

每组数据第一行包含两个正整数n,m(1<=n,m<=2000)，表示序列的长度。

第二行包含n个正整数，表示a[0],a[1],…,a[n-1] (0<=a[i]<=1000000)。

第三行包含m个正整数，表示b[0],b[1],…,b[m-1] (0<=b[i]<=1000000)。

Output

对于每组数据输出一行一个整数，即答案。

Sample Input

Sample Output

HINT

注意：此题只有一个数据点。

Solution

O(n)-O(1) gcd

首先预处理出$\sqrt n$ 内两两的gcd，对于大数，最坏情况下一定可以分解成两个质数加一个小于$\sqrt n$ 的数，对于质数单独算贡献，对于小数用于处理的算。

Code

 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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned unt;
typedef long long LL;
unt p[1000001], e[1000001], d[1000001][3], G[1001][1001], cnt;
void pretreat() {
    for (unt i = 2u; i <= 1000000u; ++i) {
        if (d[i][0] == 0u) { p[cnt++] = i; e[i] = i; }
        for (unt j = 0u; j < cnt; ++j) {
            if (LL(i) * LL(p[j]) > LL(1000000u)) break;
            d[i*p[j]][0] = 1u;
            e[i*p[j]] = p[j];
            if (i%p[j] == 0u) break;
        }
    }
    d[1][0] = d[1][1] = d[1][2] = 1u;
    for (unt i = 2; i <= 1000000u; ++i) {
        d[i][0] = d[i/e[i]][0];
        d[i][1] = d[i/e[i]][1];
        d[i][2] = d[i/e[i]][2];
        if (d[i][0] * e[i] <= 1000u) d[i][0] *= e[i];
        else if (d[i][1] * e[i] <= 1000u) d[i][1] *= e[i];
        else d[i][2] *= e[i];
    }
}
inline unt GCD(unt x, unt y) {
    if (x <= 1000u && y <= 1000u) return G[x][y];
    if (x == 0u || y == 0u) return x + y;
    unt ret = 1u, tmp, val;
    for (register int i = 0; i < 3; ++i) {
        tmp = d[x][i];
        if (tmp <= 1000u) val = G[tmp][y % tmp];
        else if (y % tmp == 0u) val = tmp;
        else val = 1u;
        ret *= val;
        y /= val;
    }
    return ret;
}
unt calc(unt x, unt y) {
    if (G[x][y] != 0u) return G[x][y];
    if (y == 0u) return G[x][y] = x;
    return G[x][y] = calc(y, x % y);
}
inline void rei(int &x) {
    x = 0; register char c = getchar();
    for (;'0'>c||c>'9';c=getchar());
    for (;'0'<=c&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c-'0');
}
inline void re(unt &x) {
    x = 0; register char c = getchar();
    for (;'0'>c||c>'9';c=getchar());
    for (;'0'<=c&&c<='9';c=getchar())x=(x<<3)+(x<<1)+(c-'0');
}
int main() {
    register int T, n, m, i, j;
    pretreat();
    for (i = 1; i <= 1000; ++i)
        for (j = 1; j <= 1000; ++j)
            G[i][j] = calc(i, j);
    rei(T);
    while (T--) {
        cnt = 0u;
        rei(n); rei(m);
        for (i = 0; i < n; ++i) re(e[i]);
        for (i = 0; i < m; ++i) re(p[i]);
        for (i = 0; i < n; ++i)
            for (j = 0; j < m; ++j)
                cnt += GCD(e[i], p[j]) ^ i ^ j;
        printf("%u\n", cnt);
    }
}