4454: C Language Practice

Time Limit: 20 Sec  Memory Limit: 24 MB
Submit: 501  Solved: 112
[Submit][Status][Discuss]

Description

BZOJ 4454: C Language Practice-LMLPHP

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

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

Source

 

[Submit][Status][Discuss]

$O(N)-O(1)$的gcd黑科技

 #include <cstdio>

 inline char Char(void)
{
static const int siz = ; static char buf[siz];
static char *hd = buf + siz;
static char *tl = buf + siz; if (hd == tl)
fread(hd = buf, , siz, stdin); return *hd++;
} inline int Int(void)
{
int ret = , neg = , c = Char(); for (; c < ; c = Char())
if (c == '-')neg ^= true; for (; c > ; c = Char())
ret = ret * + c - ''; return neg ? -ret : ret;
} int g[][]; int fac[][]; int pre[], pri[], tot; inline int gcd(int a, int b)
{
if (a <= && b <= )
return g[a][b]; int ret = ; for (int i = ; i < ; ++i)
if (fac[a][i] != )
{
int t = fac[a][i]; if (pre[t])
{
int d = g[t][b % t];
ret *= d, b /= d;
}
else if (b % t == )
ret *= t, b /= t;
} return ret;
} signed main(void)
{
for (int i = ; i <= ; ++i)
for (int j = ; j <= ; ++j)
if (i == || j == )
g[i][j] = i + j;
else if (g[j][i % j])
g[i][j] = g[j][i % j];
else if (g[i % j][j])
g[i][j] = g[i % j][j];
else if (g[i][j % i])
g[i][j] = g[i][j % i];
else if (g[j % i][i])
g[i][j] = g[j % i][i]; fac[][] = fac[][] = fac[][] = ; for (int i = ; i <= ; ++i)
{
if (!pre[i])pri[++tot] = i,
fac[i][] = fac[i][] = , fac[i][] = i; for (int j = ; j <= tot && pri[j] * i <= ; ++j)
{
int num = pri[j] * i, p = pri[j]; pre[num] = p;
fac[num][] = fac[i][];
fac[num][] = fac[i][];
fac[num][] = fac[i][]; if (fac[num][] * p <= )
fac[num][] *= p;
else if (fac[num][] * p <= )
fac[num][] *= p;
else
fac[num][] *= p;
}
} for (int cas = Int(); cas--; )
{
static int n, m, a[], b[]; n = Int();
m = Int(); for (int i = ; i < n; ++i)
a[i] = Int(); for (int i = ; i < m; ++i)
b[i] = Int(); unsigned ans = ; for (int i = ; i < n; ++i)
for (int j = ; j < m; ++j)
ans += gcd(a[i], b[j]) ^ i ^ j; printf("%u\n", ans);
}
}

@Author: YouSiki

05-11 09:36
查看更多