[BZOJ4659/2694] Lcm

题目描述

Description


对于任意的>1的n gcd(a, b)不是n^2的倍数
也就是说gcd(a, b)没有一个因子的次数>=2

Input

一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

4
2 4
3 3
6 5
8 3

Sample Output

24
28
233
178

HINT

T <= 10000
N, M<=4000000

题目分析

根据莫比乌斯函数的定义 得到:题目要求出i=1nj=1mμ(gcd(i,j))2lcm(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} \mu(gcd(i,j))^2*lcm(i,j)
=i=1nj=1md=1nijd[gcd(i,j)=1]μ(d)2 =\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d=1}^{n}\frac{i*j}{d}[gcd(i,j)=1]\mu(d)^2
=d=1nμ(d)2i=1ndj=1mdkgcd(i,j)ijdμ(k) =\sum\limits_{d=1}^{n}\mu(d)^2\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum\limits_{k|gcd(i,j)}i*j*d*\mu(k)
=d=1ndμ(d)2k=1ndμ(k)k2i=1ndkij=1mdkj =\sum\limits_{d=1}^{n}d*\mu(d)^2\sum\limits_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)*k^2\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor }i \sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}j
D=dkD=dk
=D=1ni=1nDij=1mDjkDkμ(k)μ(Dk) =\sum\limits_{D=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{D} \rfloor }i \sum\limits_{j=1}^{\lfloor \frac{m}{D} \rfloor}j\sum\limits_{k|D}k*\mu(k)*\mu(\frac{D}{k})
快筛出kDkμ(k)μ(Dk)\sum\limits_{k|D}k*\mu(k)*\mu(\frac{D}{k})即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
long long mod=1ll<<30;
int prime[4000100];
bool vis[4000100];
long long f[4000100],sum[4000100];
void init()
{
    f[1]=1,sum[1]=1;
    for(int i=2;i<=4000000;i++)
    {
        if(!vis[i]) 
            prime[++prime[0]]=i,f[i]=1-i;
        sum[i]=(sum[i-1]+i)%mod;
        for(int j=1;j<=prime[0]&&i*prime[j]<=4000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]) f[i*prime[j]]=(f[i]*f[prime[j]])%mod;
            else if(i%(prime[j]*prime[j])!=0) f[i*prime[j]]=(f[i/prime[j]]*(-prime[j])+mod)%mod; 
        }
    }
    for(int i=1;i<=4000000;i++) f[i]=(((long long)f[i]*i)%mod+f[i-1]+mod)%mod;
}
void work(int x,int y)
{
    int last=0;
    if(x>y) swap(x,y);
    long long ans=0;
    for(int i=1;i<=x;i=last+1)
    {
        last=min(x/(x/i),y/(y/i));
        ans=(ans+((f[last]-f[i-1]+mod)%mod)*(sum[x/i]*sum[y/i])%mod)%mod;
    }
    printf("%lld\n",ans);
}
int main()
{   
    init();
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&m),work(n,m);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注