Loj #528. 「LibreOJ β Round #4」求和 (莫比乌斯反演)

题目链接：https://loj.ac/problem/528

题目：给定两个正整数N,M，你需要计算ΣΣu(gcd(i,j))^2 mod 998244353 ,其中i属于[1,N],j属于[1,M]

解题思路：

代码：

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
typedef long long ll;
const int maxn=1e7+7;
const int mod=998244353;
ll n,m,mu[maxn],sum[maxn],prime[maxn],tot;
void getMobius(int N){
    for(int i=1;i<=N;i++)prime[i]=1;
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(prime[i]){
            prime[tot++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<tot&&i*prime[j]<=N;j++){
            prime[i*prime[j]]=0;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}
ll solve(ll a,ll b){
    ll res=0;
    for(ll l=1,r;l<=a;l=r+1){
        r=min(a/(a/l),b/(b/l));
        ll x=(sum[(int)sqrt(r)]-sum[(int)sqrt(l-1)]+mod)%mod,y=(a/l)%mod,z=(b/l)%mod;
        res=(res+x*y%mod*z%mod)%mod;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&n,&m);
    if(n>m) swap(n,m);
    getMobius(1e7);
    sum[1]=1;
    for(int i=2;i<=1e7;i++) sum[i]=sum[i-1]+mu[i];
    printf("%lld
",solve(n,m));
    return 0;
}