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

求值：

易得原式如下：

枚举最大公因数：

非常经典的式子的化法：

式子的后半段出现了互质数对之积之和，考率先单独拿出来,记

有：

观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记

可以求解。

至此：

我们可以数论分块求解这部分。

回到定义的地方，则原式为：

这又是一个可以数论分块求解的式子。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+7,mod=20101009;
int mu[maxn];
ll f[maxn];
int g(ll x,ll y) {
    return (x*(x+1)/2%mod)*(y*(y+1)/2%mod)%mod;
}
int sum(int n,int m) {
    int res(0);
    for(int d=1,x,y,r;d<=n;++d) {
        x=n/d,y=m/d;
        r=min(n/x,m/y);
        res=(res+(f[r]-f[d-1])*g(x,y))%mod;
        d=r;
    }
    return res;
}
bool vis[maxn];
vector<int>prime;
inline void init(int n) {
    f[1]=mu[1]=1;
    for(int i=2;i<=n;++i) {
        if(!vis[i]) {
            prime.emplace_back(i); mu[i]=-1;
        }
        for(auto &j:prime) {
            if(i*j>n) break;
            vis[i*j]=1;
            if(i%j==0) break;
            mu[i*j]=-mu[i];
        }
        f[i]=(f[i-1]+(ll)i*i*mu[i])%mod;
    }
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    if(n>m) swap(n,m);//便于处理
    init(n);
    int ans(0);
    for(int d=1,x,y,r;d<=n;++d) {
        x=n/d,y=m/d;
        r=min(n/x,m/y);
        ans=(ans+(ll)(r+d)*(r-d+1)/2*sum(x,y))%mod;
        d=r;
    }
    cout<<(ans+mod)%mod<<'\n';
    return 0;
}

这题线性筛比普通筛快很多。