题目名称

小A的数学题

题目大意

给定n、m,求 ${\sum }_{i=1}^n{\sum }_{j=1}^{m}gcd(i,j{)}^2\backslash sum\_\{i=1\}^n\backslash sum\_\{j=1\}^mgcd(i,j)^2$

实现思路

容斥原理：
易知gcd(i,j)范围是1~min(n,m),因此枚举gcd即可
求出每个gcd的数目cnt[]
答案为：ans+=gcd*gcd*cnt[gcd]
gcd=i时，i的数目为(n/i)*(m/i),但是i的倍数也被包含了，因此可减去cnt[i*2]...cnt[i*k],其中i*k<=min(n,m)
i*(k+1)>min(n,m);减去后得到的值为最终i的数目。在减去的过程中我们要知道cnt[i*倍数]的数目，但实际上我们事先求得的数目不一定准确，因此要倒序枚举gcd，即从min(n,m)开始，因为cnt[min(n,m)]一定是准确的。更新cnt[i]的值即可。
求ans时注意不断取模。

很明显 莫比乌斯反演也能写，读者自己思考。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
const int maxn=1e6+7;
const int mod=1e9+7;
ll cnt[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    int s=min(n,m);
    ll ans=0;
    for(int i=s;i>=1;i--)
    {
        cnt[i]=(ll)n/i*(m/i);
    }
    for(ll i=s;i>=1;i--)
    {
        ll x=cnt[i];
        for(int j=i*2;j<=s;j+=i)
            x-=cnt[j];
        cnt[i]=x;
        ans=(ans%mod+(((i*i)%mod)*x)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}