[SDOI2014]数表

Link
对于

$\sum_{i = 1}^N \sum_{j = 1}^M F(gcd(i, j))$

这个式子来说，我们首先把它变换一下
改变枚举顺序

$\sum_{d = 1} ^{N} F(d) \sum_{i = 1} ^ N \sum_{j = 1} ^ M [gcd(i,j) == d]$

把$d$除过去

$\sum_{d = 1} ^{N} F(d) \sum_{i = 1} ^ {N / d} \sum_{j = 1} ^ {M / d} [gcd(i,j) == 1]$

把最后的式子莫比乌斯反演一下

$\sum_{d = 1} ^{N} F(d) \sum_{i = 1} ^ {N / d} \sum_{j = 1} ^ {M / d} \sum _{x | i, x | j} \mu (x)$

把$x$的枚举挪到前面去。

$\sum_{d = 1} ^{N} F(d) \sum _{x = 1} ^ {N / d}\mu (x) \lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor$

设$T = dx$，然后再变一下枚举顺序。

$\sum _{T = 1} ^ {N / d}\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{d | T} F(d) \mu (\frac{T}{d})$

然后发现出现了狄雷克利卷积，这就非常棒。然后我们记一个

$G(T) = \sum_{d | T} F(d) \mu (\frac{T}{d})$

然后式子变成

$\sum _{T = 1} ^ {N / d}\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor G(T)$

这道题比较难的地方就在于其要求不大于$a$。于是我们将原来的$F(x)$函数加上一个$a$的限制。然后发现$F(d) \leq a$时对答案产生贡献。
对于随着$a$的变化而变化的$G(x)$，采取离线筛选然后升序排序的情况。
然后问题转化成了一个很熟悉的形式：

每次加入$d$满足$F(d) \leq a$
查询前缀和。
然后我们就可以用树状数组来进行维护。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const long long MAXN = 100010 ;
const long long MAXM = 100010 ;
const long long Inf = 0x7fffffff ;
const long long Mod = (1LL << 31) ;

long long T ;
long long U[MAXN], F[MAXN], S[MAXN], P[MAXN] ;
long long Sum[MAXN], Ans[MAXN], Tot, B[MAXN] ;
struct Node {
    long long N, M, A, Num ;
    bool operator < (const Node & Y) const {
        return A < Y.A ;
    }
}   E[MAXN] ;
struct Node2 {
    long long X ;
    bool operator < (const Node2 & Y) const {
        return S[X] < S[Y.X] ;
    }
}   G[MAXN] ;

inline long long Read() {
    long long X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline void Init () {
    S[1] = U[1] = 1 ;
    for (long long i = 2 ; i <= MAXN ; i ++) {
        if (! B[i]) {
            P[Tot ++] = i ; U[i] = - 1 ;
            S[i] = i + 1 ; F[i] = i + 1 ;
        }
        for (long long j = 0 ; j < Tot ; j ++) {
            if (i * P[j] > MAXN) break ;
            B[i * P[j]] = 1 ; 
            if (i % P[j] == 0) {
                U[i * P[j]] = 0 ; 
                F[i * P[j]] = F[i] * P[j] + 1 ;
                S[i * P[j]] = S[i] / F[i] * F[i * P[j]] ;
                break ;
            }
            U[i * P[j]] = - U[i] ; 
            F[i * P[j]] = P[j] + 1 ;
            S[i * P[j]] = S[i] * (P[j] + 1) ;
        }
    }
    for (long long i = 1 ; i <= MAXN ; i ++) G[i].X = i ;
    sort(G + 1, G + MAXN + 1) ;
}

inline long long Lowbit(long long Now) { return Now & (- Now) ; } ;

inline void Add(long long Now, long long K) {
    while (Now <= MAXN) {
        Sum[Now] = ((LL) Sum[Now] + K) % Mod ;
        Now += Lowbit(Now) ;
    }   return ;
}

inline void Change(long long Now) {
    for (long long i = 1 ; i * Now <= MAXN ; i ++) {
        // cout << U[i] << " " << S[Now]<< " " << (LL) U[i] * S[Now] % Mod << endl ;
        // system("pause") ;
        Add(Now * i, (LL) U[i] * S[Now] % Mod) ;
    }
}

inline long long Query (long long Now) {
    long long Ans = 0 ;
    while (Now >= 1) {
        Ans = ((LL) Ans + Sum[Now]) % Mod ;
        Now &= Now - 1 ;
    }   return Ans ;
}

inline long long Answer(long long L, long long R) {
    long long Ans = 0, ll = 0, rr ;
    for (long long l = 1, r ; l <= L ; l = r + 1, ll = rr) {
        r = min (L / (L / l), R / (R / l)) ;
        rr = Query(r) ;
        Ans = (Ans + ((LL) rr - ll) % Mod * (L / l) % Mod * (R / l) % Mod) % Mod;
    }   return ((LL) Ans + Mod) % Mod ;
}

int main() {
    T = Read() ; Init() ;
    for (long long i = 1 ; i <= T ; i ++) {
        E[i].N = Read(), E[i].M = Read(), E[i].A = Read() ;
        if (E[i].N > E[i].M) swap(E[i].N, E[i].M) ;
        E[i].Num = i ;
    }
    sort(E + 1, E + T + 1) ; long long j = 1 ;
    for (long long i = 1 ; i <= T ; i ++) {
        for (; j <= MAXN && S[G[j].X] <= E[i].A ; j ++)
            Change(G[j].X) ;
        Ans[E[i].Num] = Answer(E[i].N, E[i].M) ;
    }
    for (long long i = 1 ; i <= T ; i ++)
        printf("%lld\n", Ans[i]) ;
    return 0 ;
}