[BZOJ2694] Lcm

题目大意

定义整数$a,b$，求所有满足一下条件的二元组$(i,j)$的$\rm lcm(i,j)$的和。

• $1\leqslant i\leqslant a,1\leqslant j\leqslant b$。
• $\forall n>1,n^2\not \mid \gcd(i,j)$。

solution

注意到第二个条件可以写成$\mu^2(\gcd(i,j))$，那么我们可以直接形式化的写出式子：

$$\sum_{i=1}^{a}\sum_{j=1}^{b}\mu^2(\gcd(i,j)){\rm lcm}(i,j)$$

随便推一下：

$$\begin{align} &\sum_{i=1}^{a}\sum_{j=1}^{b}\mu^2(\gcd(i,j)){\rm lcm}(i,j)\\ =&\sum_{d=1}^{a}\frac{\mu^2(d)}{d}\sum_{i=1}^{a}\sum_{j=1}^{b}ij[\gcd(i,j)=d]\\ =&\sum_{d=1}^{a}d\mu^2(d)\sum_{i=1}^{a/d}\sum_{j=1}^{b/d}\sum_{t|i,t|j}\mu(t)ij\\ =&\sum_{d=1}^{a}d\mu^2(d)\sum_{t=1}^{a/d}\mu(t)t^2s(\lfloor\frac{a}{dt}\rfloor)s(\lfloor\frac{b}{dt}\rfloor) \\ =&\sum_{T=1}^{a}s(\lfloor\frac{a}{T}\rfloor)s(\lfloor\frac{b}{T}\rfloor)\sum_{d|T}\mu^2(d)\mu(\frac{T}{d})\frac{T^2}{d} \\ \end{align}$$

后面那个求和可以预处理，前面整除分块，复杂度就是$O(n\log n+T\sqrt{n})$.

Code

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 4e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int f[maxn],mu[maxn],pri[maxn],vis[maxn],tot,a,b,t;

void sieve() {
    mu[1]=1;
    for(int i=2;i<maxn;i++) {
        if(!vis[i]) mu[i]=-1,pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<maxn;j++) {
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            mu[i*pri[j]]=-mu[i];
        }
    }
    for(int d=1;d<maxn;d++)
        if(mu[d]) 
            for(int t=d;t<maxn;t+=d)
                f[t]+=mu[t/d]*t*(t/d);
    for(int i=1;i<maxn;i++) f[i]+=f[i-1];
}

int s(int n) {return 1ll*n*(n+1)/2;}

int main() {
    read(t);sieve();
    while(t--) {
        read(a),read(b);if(a>b) swap(a,b);
        int res=0,T=1;
        while(T<=a) {
            int pre=T;T=min(a/(a/T),b/(b/T));
            res+=s(a/T)*s(b/T)*(f[T]-f[pre-1]);T++;
        }write(res&((1<<30)-1));
    }
    return 0;
}