bzoj3561（莫比乌斯反演）

传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3561
题面：
给定n,m
求i=1∑n​j=1∑m​lcm(i,j)gcd(i,j)

solution：
比较简单的莫比乌斯反演吧
直接推式子就完事了(假定m≤n)
i=1∑n​j=1∑m​(gcd(i,j)ij​)gcd(i,j)=d=1∑m​ddi=1∑⌊dn​⌋​j=1∑⌊dm​⌋​(ij)k[gcd(i,j)==1]=d=1∑m​ddt=1∑⌊dm​⌋​μ(t)t2di=1∑⌊tdn​⌋​idj=1∑⌊tdm​⌋​jd
直接预处理就好了
复杂度O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i =  k[x];i;i = e[i].n)
#define P pair<int,int>
#define Pil pair<int,ll>
#define Pli pair<ll,int>
#define Pll pair<ll,ll>
#define pb push_back 
#define pc putchar
#define mp make_pair
#define file(k) memset(k,0,sizeof(k))
#define ll long long
#define N 500000
int rd()
{
	int num = 0;char c = getchar();bool flag = true;
	while(c < \'0\'||c > \'9\') {if(c == \'-\') flag = false;c = getchar();}
	while(c >= \'0\' && c <= \'9\') num = num*10+c-48,c = getchar();
	if(flag) return num;else return -num;
}
const int p = 1e9+7;
int n,m;
int v[500100],sum[500100];
int prime[500100],miu[500100];
bool flag[500100];
inline int mul(int a,int b){return 1ll*a*b%p;}
inline int calc(int a,int b){return (a+=b)>=p?a-=p:a;}
inline int ksm(int a,int x){int now=1;for(;x;x>>=1,a=1ll*a*a%p)if(x&1)now=1ll*now*a%p;return now;}
int main()
{ 
    n = rd();m = rd();miu[1] = 1;
    if(n<m) swap(n,m);
    rep(i,2,N)
    {
    	if(!flag[i]) prime[++prime[0]] = i,miu[i] = p-1;
    	rep(j,1,prime[0])
    	{
    		if(i*prime[j]>N) break;
    		flag[i*prime[j]] = true;
    		if(i%prime[j] == 0) break;
    	    miu[i*prime[j]] = p-miu[i];
		}
    }
    rep(i,1,n) v[i] = 1,sum[i] = calc(sum[i-1],v[i]);
    int ans = 0;
	rep(d,1,m)
	{
		int sigma = 0;
		rep(i,1,n/d) v[i] = mul(v[i],i),sum[i] = calc(sum[i-1],v[i]);
	    rep(t,1,m/d) 
		     miu[t] = mul(miu[t],mul(t,t)),
			 sigma = calc( sigma , mul( miu[t] , mul( sum[n/(t*d)] , sum[m/(t*d)] ) ) );
	    ans = calc(ans,mul(sigma,ksm(d,d)));
	}
	printf(\"%d\\n\",ans);
	return 0;
}