梦想熟练掌握莫比乌斯反演

[CQOI2007]余数求和

纯数论分块板子题不谈~不过要注意右边界不要大于n，因为k可能大于n，并且注意除以0的情况就好了

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m,ans=0;
	scanf("%lld%lld",&n,&m);
	ans+=n*m;
	for(long long l=1,r=0;l<=n;l=r+1)
	{
		if(m/l) r=min(n,m/(m/l));
		else r=n;
		ans-=(m/l)*(l+r)*(r-l+1)/2;
	}
	printf("%lld",ans);
}

[清华集训2012]模积和

先算出全部的然后减去i=j的。注意这里i=j的时候需要化简(n-[n/i]i)(m-[m/i]i)化简出来四项式子之后我们数论分块的r标准为min(n/(n/l),m/(m/l))即可
注意平方和公式为x(x+1)*(2x+1)/6

#include <bits/stdc++.h>
using namespace std;
long long mod=19940417;
long long sum(long long x)
{
    return x%mod*(x+1)%mod*(2*x+1)%mod*3323403%mod;
}
int main()
{
    long long ans1=0,ans2=0,ans,jk,n,m,inv=9970209;
    scanf("%lld%lld",&n,&m);
    ans1+=n*n,ans2+=m*m;
    ans1%=mod,ans2%=mod;
    for(long long l=1,r=0;l<=n;l=r+1)
    {
        if(n/l) r=n/(n/l);
        else r=n;
        ans1=ans1%mod-(n/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod;
        ans1%=mod;
    }
    for(long long l=1,r=0;l<=m;l=r+1)
    {
        if(m/l) r=m/(m/l);
        else r=m;
        ans2=ans2%mod-(m/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod;
        ans2%=mod;
    }
    ans1=(ans1%mod+mod)%mod;
    ans2=(ans2%mod+mod)%mod;
    ans=ans1*ans2;
    ans%=mod;
    jk=min(n,m);
    ans=ans%mod-n%mod*m%mod*jk%mod;
    ans%=mod;
    for(long long l=1,r=0;l<=jk;l=r+1)
    {
        if(n/l||m/l) r=min(n/(n/l),m/(m/l));
        else r=jk;
        ans=ans%mod+m%mod*(n/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod+n%mod*(m/l)%mod*(l+r)%mod*(r-l+1)%mod*inv%mod-(n/l)%mod*(m/l)%mod*(sum(r)%mod-sum(l-1)%mod)%mod;
        ans%=mod;
    }
    printf("%lld",(ans%mod+mod)%mod);
}