P1829 [国家集训队]Crash的数字表格 / JZPTAB

不错的莫反练手题，可以说把大部分套路都涵盖了。

不妨令 $n\le m$，让我们求：

$$\sum_{i=1}^n \sum_{j=1}^{m} \text{lcm}(i,j)$$

先转换为我们熟悉的 $\gcd$：

$$\sum_{i=1}^n \sum_{j=1}^{m} \frac{i\cdot j}{\gcd(i,j)}$$

枚举 $\gcd(i,j)$：

$$\sum_{k=1}^{n} \sum_{i=1}^n \sum_{j=1}^{m} \frac{i\cdot j \cdot [\gcd(i,j)=k]}{k}$$

变换为 $[\gcd(i,j)=1]$ 的形式：

$$\sum_ {k=1} ^ {n} \sum_ {i=1} ^ {\lfloor \frac{n}{k}\rfloor} \sum_ {j=1} ^ {\lfloor \frac{m}{k}\rfloor} {i\cdot j \cdot k \cdot [\gcd(i,j)=1]}$$

根据经典式子 $[\gcd(i,j)=1]=\sum\limits_{d|\gcd(i,j)} \mu(d)$，进一步得到：

$$\sum_ {k=1} ^ {n} \sum_ {i=1} ^ {\lfloor \frac{n}{k}\rfloor} \sum_ {j=1} ^ {\lfloor \frac{m}{k}\rfloor} \sum_{d|\gcd(i,j)} \mu(d) \cdot {i\cdot j \cdot k }$$

把 $d$ 提到前面去，尝试枚举 $d$：

$$\sum_ {k=1} ^ {n} \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d) \cdot k \cdot d^2\sum_ {i=1} ^ {\lfloor\frac {n}{kd}\rfloor} \sum_ {j=1} ^ {\lfloor\frac{m}{kd}\rfloor}{i\cdot j}$$

把 $kd$ 看做一个整体，设 $kd=T$，又得到：

$$\sum_ {T=1} ^ {n} T\sum_{d|T}\mu(d) \cdot d\sum_ {i=1} ^ {\lfloor\frac {n}{T}\rfloor} \sum_ {j=1} ^ {\lfloor\frac{m}{T}\rfloor}{i\cdot j}$$

最后面是个等差数列求和，并且可以整数分块做。考虑如何求 $f(x)=\sum\limits_{d|x}\mu(d)\cdot d$，很容易知道这是个积性函数，考虑在线性筛的过程中如何求，设 $x=i\cdot j$ ，其中 $j$ 为 $x$ 最小的质因子：

1.$x\in \text{prime}$ ，$f(x)=-x+1$。

2.$j$ 为 $i$ 的质因子，那么 $j$ 对 $f(x)$ 是没有贡献的，$f(x)=f(i)$。

3.$j$ 不为 $i$ 的质因子，那么根据积性函数的定义，$f(x)=f(i)\cdot f(j)$。

时间复杂度 $\mathcal O(n+T\sqrt n)$，$T$ 为询问总数，不过洛谷上这道题只有一个询问。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7+10,mod=20101009;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int T,n,m;
int cnt,prime[N],vis[N],f[N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
inline void sieve(int n)
{
    f[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
            f[i]=mod-i+1,prime[++cnt]=i;
        for(int j=1;j<=cnt&&1ll*i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                f[i*prime[j]]=f[i];
                break;
            }
            f[i*prime[j]]=1ll*f[i]*f[prime[j]]%mod;
        }
    }
    for(int i=1;i<=n;i++)
       f[i]=adj(f[i-1]+1ll*f[i]*i%mod);
}
inline int sum(int x,int y)
{
    return (1ll*(x+1)*x/2)%mod*(1ll*(y+1)*y/2%mod)%mod;
}
inline int solve(int n,int m)
{
    int res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res=adj(res+1ll*adj(f[r]-f[l-1]+mod)*sum(n/l,m/l)%mod);
    }
    return res;
}
int main()
{
    sieve(N-10);
    T=1;
    while(T--)
    {
        read(n,m);
        if(n>m)swap(n,m);
        printf("%d\n",solve(n,m));
    }
    return 0;
}