【问题描述】
太阳神拉很喜欢最小公倍数，有一天他想到了一个关于最小公倍数的题目。
求满足如下条件的数对(a,b)对数:a,b均为正整数且a,b<=n而lcm(a,b)>n。其中的lcm当然表示最小公倍数。答案对1,000,000,007取模

【输入格式】
第一行一个正整数n。
【输出格式】
一行一个整数表示答案，对1,000,000,007取模。

【样例输入输出】
ra.in
3
ra.out
2

【数据范围与约定】
对于20%的数据n<=2000；
对于40%的数据n<=10000000；
对于60%的数据n<=100000000；
对于80%的数据n<=1000000000；
对于100%的数据n<=10000000000

分析：

以下内容是搬运+整理

受“序列计数”的启发，用一个小小的容斥，

用n^2减去lcm(a,b)<=n的对数

我们枚举d=gcd(a,b)，令a’=a/d,b’=b/d;
则
a=a’d,
b=b’d
lcm(a,b)=a’d*b’d/d=a’b’d<=n

即我们要求的是
gcd(a’,b’)=1 //不然gcd(a,b)!=d
且a’b’d<=n的三元组(a’,b’,d)个数

反演一下：

美化一下

这里i是小于等于n^0.5的，因此我们可以线筛出μ函数的值
现在问题在于如何求满足abc<=m的三元组个数
我们可以限定a<=b<=c，先计算满足这个条件的三元组个数
显然a可以在m^(1/3)的范围内枚举，
b可以在(m/a)^0.5的范围内枚举，
c的个数可以直接O(1)计算

总的时间复杂度O(n^(2/3))

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define ll long long

using namespace std;

const int mod=1000000007;
const int N=100005;
int n,ans=0;
int sshu[N],tot=0,mu[N];
bool no[N];

void doit()
{
    int i;
    memset(no,0,sizeof(no));
    mu[1]=1;
    for (i=2;i<=N;i++)
    {
        if (!no[i])
        {
            mu[i]=-1;  //素数 
            sshu[++tot]=i;
        }
        for (int j=1;j<=tot&&sshu[j]*i<=N;j++)
        {
            no[i*sshu[j]]=1; 
            if (i%sshu[j]==0)
            {
                mu[i*sshu[j]]=0;  //含平方因子 
                break;
            }
            mu[i*sshu[j]]=-mu[i];  //积性函数 
        }
    }
    int unit=trunc(sqrt(n));
    for (int i=1;i<=unit;i++)
    {
        int cnt;
        if (!mu[i]) continue;
        ll x=n/(1ll*i*i);
        cnt=0;
        for (int a=1;(ll)1ll*a*a*a<=x;a++)
        {
            int lb=trunc(sqrt(x/a));
            cnt-=2; cnt%=mod; cnt+=mod; cnt%=mod;
        }
        int la=trunc(sqrt(x));
        for (int a=1;a<=la;a++)
            cnt=(cnt-(x/1ll*a*a)*3%mod)%mod,cnt%=mod,cnt+=mod,cnt%=mod;
        ans=(ans+cnt*1ll*(n%mod)*(n%mod)%mod+mod)%mod;
    }
    ans=(((n%mod)*(n%mod)%mod-ans)%mod+mod)%mod;
}

int main()
{
    //freopen("ra.in","r",stdin);  
    //freopen("ra.out","w",stdout);
    scanf("%d",&n);
    doit();
    printf("%d",ans);
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：太阳神，转载请注明来源！