题解 SP26045 GCDMAT2 - GCD OF MATRIX (hard)

· · 题解

思路

这题是 SP26017 GCDMAT - GCD OF MATRIX 的卡常版。

式子的推导在 题解 SP26017 GCDMAT - GCD OF MATRIX。

先用线性筛预处理欧拉函数，再计算欧拉函数的前缀和，最后对于每个询问用数论分块计算答案即可。

但是这样常数太大，过不了。

因为除法很耗时，而这个式子中出现了大量的除法，所以可以预处理除数的倒数，把除法转换成乘法。

这样就能过了。

时间复杂度为 \mathcal { O } ( n + m + T \sqrt { n + m } )。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e6;
int T;
int n, m;
int i1, j1, i2, j2;
vector < int > pri;
bool vis[MAXN + 5];
int phi[MAXN + 5];
int sum[MAXN + 5];
double inv[MAXN + 5];
void Init(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i ++){
        if(vis[i] == false){
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for(int j : pri){
            if(i * j > n) break;
            vis[i * j] = true;
            if(i % j == 0){
                phi[i * j] = phi[i] * j;
                break;
            }
            phi[i * j] = phi[i] * (j - 1);
        }
    }
    for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + phi[i];
    for(int i = 1; i <= n; i ++) inv[i] = (1.00000000 / i) * 1.00000001;
}
int S(int n, int m)
{
    int res = 0;
    for(int l = 1, r; l <= min(n, m); l = r + 1){
        r = min((n * inv[((int)(n * inv[l]))]), (m * inv[((int)(m * inv[l]))]));
        res = (res + ((int)(n * inv[l])) % MOD * ((int)(m * inv[l])) % MOD * (sum[r] - sum[l - 1]) % MOD) % MOD;
    }
    return res;
}
signed main()
{
    scanf("%lld", &T);
    scanf("%lld%lld", &n, &m);
    Init(max(n, m));
    while(T --){
        scanf("%lld%lld%lld%lld", &i1, &j1, &i2, &j2);
        printf("%lld\n", ((S(i2, j2) - S(i1 - 1, j2) - S(i2, j1 - 1) + S(i1 - 1, j1 - 1)) % MOD + MOD) % MOD);
    }
    return 0;
}

2022.8.20