P2257 YY的GCD

求

\[\begin{aligned} & \sum^{n}_{i = 1} \sum^{m}_{j = 1} [ gcd(i, j) \in prime]\\ & \sum^{}_{k \in prime} \sum^{n}_{i = 1} \sum^{m}_{j = 1}[ gcd(i, j) = k]\\ \end{aligned} \]

设

\[\begin{aligned} f(s) & = \sum^{n}_{i = 1} \sum^{m}_{j = 1}[ gcd(i, j) = s]\\ g(s) & = \sum^{}_{s \mid k} f(k) \end{aligned} \]

有

\[\begin{aligned} & g(s) = [\dfrac{n}{s}][\dfrac{m}{s}]\\ & f(s) = \sum^{}_{s \mid k} \mu(\dfrac{k}{s})g(k)\\ & f(s) = \sum^{}_{s \mid k} \mu(\dfrac{k}{s})[\dfrac{n}{k}][\dfrac{m}{k}]\\ \end{aligned} \]

\[\begin{aligned} Ans = \sum^{}_{s \in prime} f(s) &= \sum^{}_{s \in prime} \sum^{}_{s \mid k} \mu(\dfrac{k}{s})g(k)\\ &= \sum^{}_{s \in prime} \sum^{[\dfrac{n}{s}]}_{k = 1} \mu(k)g(ks)\\ &= \sum^{}_{s \in prime} \sum^{[\dfrac{n}{s}]}_{k = 1} \mu(k)g(T)\\ &= \sum^{}_{k\in prime} \sum^{[\dfrac{n}{k}]}_{d = 1} \mu(d)[\dfrac{n}{T}][\dfrac{m}{T}](T = dk)\\ &= \sum^{}_{k\in prime} \sum^{n}_{T = 1} \mu (\dfrac{T}{k})[\dfrac{n}{T}][\dfrac{m}{T}](T = dk)\\ &= \sum^{n}_{T = 1} \sum^{}_{k \mid T, k\in prime} \mu (\dfrac{T}{k})[\dfrac{n}{T}][\dfrac{m}{T}](T = dk)\\ &=\sum^{n}_{T = 1} [\dfrac{n}{T}][\dfrac{m}{T}] \sum _{k \mid T, k \in prime} \mu(\dfrac{T}{k})(T = dk)\\ &=\sum^{n}_{T = 1} [\dfrac{n}{T}][\dfrac{m}{T}] e(T)(T = dk)\\ e(T) &=\sum _{k \mid T, k \in prime} \mu(\dfrac{T}{k}) \end{aligned} \]

枚举质数 \(k\) ，再枚举 \(k\) 的倍数 \(T\) , \(e(T) += \mu (\dfrac{T}{k})\)，即可计算 \(e(T)\)。

其中 \(n \le m\)。

在套个数论分块就完了？

好难。。。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(ll i = (a); i <= (b); i ++)
#define Rep(i, a, b) for(ll i = (a); i >= (b); i --)
const ll N = 1e7 + 11;
ll mu[N], vis[N];
ll e[N];
vector<ll> prime;
void Table(ll M){
    mu[1] = 1;
    For(i, 2, M){
        if(vis[i] == 0){
            vis[i] = i;
            prime.push_back(i);
            mu[i] = -1;
        }
        for(auto j:prime){
            if(j * i > M)break;
            vis[i * j] = j;
            if(i % j == 0){
                mu[i * j] = 0;
                break;
            }
            mu[i * j] = -mu[i];
        }
    }
    for(auto i:prime){
        for(ll j = 1; j * i <= M; j ++){
            e[i * j] += mu[j];
        }
    }
    for(ll i = 1; i <= M; i ++){
        e[i] += e[i - 1];
    }
    /*
    for(ll i = 1; i <= 20; i ++){
        prllf("%d %d\n", i, vis[i]);
    }
    */
    return;
}
void work(ll n, ll m){
    if(n > m)
        swap(n, m);
    ll Ans = 0, l = 1, r;
    for(; l <= n; l = r + 1){
        r=min(n/(n/l),m/(m/l));
        Ans += (e[r] - e[l - 1]) * (n / l) * (m / l);
    }
    printf("%d\n", Ans);
    return ;
}
ll Question;
int main(){
//    clock_t x = clock();
//    freopen("text.in", "r", stdin);
    Table(N - 10);
    scanf("%lld", &Question);
    while(Question --){
        ll n, m;
        scanf("%lld%lld", &n, &m);
        work(n, m);
    }
//    clock_t y = clock();
//    cout << y - x << endl;
    return 0;
}