P5435 题解

· · 题解

这题其实可以不用预处理，只需要加快计算最大公因数的速度即可。

首先，我们知道：

\gcd(a, b) = \begin{cases} \gcd(b, a - b) & a \bmod 2 = 1, b \bmod 2 = 1\\ \gcd(\frac{a}{2}, b) & a \bmod 2 = 0, b \bmod 2 = 1\\ \gcd(a, \frac{b}{2}) & a \bmod 2 = 1, b \bmod 2 = 0\\ \gcd(\frac{a}{2}, \frac{b}{2}) \times 2 & a \bmod 2 = 0, b \bmod 2 = 0\\ \end{cases}

于是，我们可以用类似二进制的方法求得最大公因数。

这里介绍一个函数：__builtin_ctz(a)，它可以返回 a 在二进制表示下末尾 0 的数量。

于是就有以下求最大公因数的代码。

typedef unsigned long long ull;

inline ull gcd(ull a, ull b){
    ull az = __builtin_ctz(a), bz = __builtin_ctz(b);
    ull z = min(az, bz);
    b >>= bz;
    while (a){
        a >>= az;
        int diff = a - b;
        az = __builtin_ctz(diff);
        b = min(a, b), a = abs(diff);
    }
    return b << z;
}

时间复杂度不会超过 \mathcal{O}(\log (\max\{a, b\}))，并且有优化。

其他部分使用普通方法即可，总体复杂度大致为 \mathcal{O}(n^2 \log a)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a));

using namespace std;

typedef unsigned long long ull;

const int maxn = 5000 + 10, mod = 998244353;

int n;
int a[maxn], b[maxn];

inline ull gcd(ull a, ull b){
    ull az = __builtin_ctz(a), bz = __builtin_ctz(b);
    ull z = min(az, bz);
    b >>= bz;
    while (a){
        a >>= az;
        int diff = a - b;
        az = __builtin_ctz(diff);
        b = min(a, b), a = abs(diff);
    }
    return b << z;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++){
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n; i++){
        ull res = 0, now = i;
        for (int j = 1; j <= n; j++){
            res = (res + (now * gcd(a[i], b[j]) % mod)) % mod;
            now = now * i % mod;
        }
        printf("%llu\n", res);
    }

return 0;
}