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

3
3 2
5 9 6
3 4
2 2
8 9
0 6
1 1
9
6

Sample Output

6
22
3

HINT

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

Solution

O(n)-O(1) gcd

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

Code

#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);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据