【题解】SPOJ GCDMAT - GCD OF MATRIX

请注意,本文编写于 99 天前,最后修改于 98 天前,其中某些信息可能已经过时。

Problem

$$ \sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}gcd(i,j) $$

Thought

$$ \sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}gcd(i,j)\\ =\sum_{i=1}^{r_1}\sum_{j=1}^{r_2}gcd(i,j)-\sum_{i=1}^{l_1-1}\sum_{j=1}^{r_2}gcd(i,j)-\sum_{i=1}^{r_1}\sum_{j=1}^{l_2-1}gcd(i,j)+\sum_{i=1}^{l_1-1}\sum_{j=1}^{l_2-1}gcd(i,j)\\ $$

设 $f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)​$

$$ f(r_1,r_2)-f(l_1-1,r_2)-f(r1,l_2-1)+f(l_1-1,l_2-1) $$

如何求 $f(n,m)​$ ?

$$ f(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\\ \sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\\ \sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}\sum_{t|gcd(i,j)}\mu(t)\\ \sum_{d=1}^{n}d\sum_{t=1}^{\frac{n}{d}}\mu(t)\frac{n}{td}\frac{m}{td} $$

$$ T=td\\ \sum_{T=1}^{n}\frac{n}{T}\frac{m}{T}\sum_{d|T}d\mu(\frac{T}{d})\\ $$

对后面部分求前缀和,对前面分块处理
发现后面是一个积性函数,可以用埃式筛筛出来(其实就是 $\phi$)

设 $H(n)=\sum_{d|n}d\mu(\frac{n}{d})$
当 $n=p^k$,则 $H(n)=p^k-p^{k-1}$

然后剩下的性质显然

注意细节!!!比如说 $phi(1)=1$ 啥的

pos = min(n / (n / i), m / (m / i));

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 50010;
const int mod = 1000000007;
bool no[N];
int pri[N], priCnt;
int phi[N], phiSum[N];
int n, m, t;

int M(int x) {
    while(x < 0) x += mod;
    while(x >= mod) x -= mod;
    return x;
}

void getPri() {
    phi[1] = phiSum[1] = 1;
    for(int i = 2; i < N; ++ i) {
        if(!no[i]) {
            pri[++ priCnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= priCnt && i * pri[j] < N; ++ j) {
            no[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break; 
            }
            else
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
        phiSum[i] = M(phiSum[i - 1] + phi[i]);
    }
}

int cal(int n, int m) {
    if(n > m) swap(n, m);
    int pos, ans = 0;
    for(int i = 1; i <= n; i = pos + 1) {
        pos = min(n / (n / i), m / (m / i));
        ans = M(1ll * M(phiSum[pos] - phiSum[i - 1]) * (n / i) % mod * (m / i) % mod + ans);
    }
    return ans;
}
int main() {
    getPri();
    t = read(); n = read(); m = read();
    while(t --) {
        int l1 = read(), l2 = read(), r1 = read(), r2 = read();
        printf("%d\n", M(M(M(cal(r1, r2) - cal(l1 - 1, r2)) - cal(r1, l2 - 1)) + cal(l1 - 1, l2 - 1)));
    }
    return 0;
}
Comments

添加新评论