[SDOI2018]旧试题

题目：

其中 表示 的约数个数。

题解：

首先有

具体证明我不会，见他人博客

设

发现了什么，这个式子是不是就是 #2476. 「2018 集训队互测 Day 3」蒜头的奖杯 中的

然后，我们来推一下这个式子，感觉这个式子还是蛮重要的。

首先:

常规莫比乌斯反演,

令

这一步我不是很看得懂，手动模拟后发现就是和的卷积后的位之和

然后我们设，原式就变成：

看那几个不爽（因为莫比乌斯反演喜欢的形式）,设

枚举然后，所以

因为一定是的倍数，一定是的倍数，我们再把换成，即枚举，A,B现在的坐标为

我们在把换成，

这是当是已知的话（即枚举），

设

如果 与 已知（同样枚举） 那么就得到了，然后考虑求后面的一部分

这很难受啊，改一下用上面推出的方法，推出

这步应该懂吧，知道了，也知道了，然后就知道了

设

经过wzp巨佬的证明，时间复杂度:

代码：

#include
using namespace std;
#define next Next
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
const int mod=1e9+7;
const int N=1e5+5;
int a[N],b[N],c[N],d[N],e[N],f[N],p[N],q[N],r[N],s[N],t[N],w[N],u[N],v[N];
int n,prim[N],cnt;
bool vis[N];
inline void add(int &a,int b)
{
    a+=b;
    if(a>=mod)a-=mod;
}
inline void jian(int &a,int b)
{
    a-=b;
    if(a<0)a+=mod;
}
inline void F(int*a,int n)//f(a)=a*u
{
    for(int i=1;i<=n;i++)
        for(int j=i+i;j<=n;j+=i)jian(a[j],a[i]);
}
inline void G(int*a,int n)//g(a)(x)=Σai[x|i] 
{
    for(int i=1;i<=cnt&&prim[i]<=n;i++)
        for(int j=n/prim[i];j;--j)
            add(a[j],a[j*prim[i]]);
}
inline void H(int*a,int n)
{
    for(int i=1;i<=cnt&&prim[i]<=n;i++)
        for(int j=1;j*prim[i]<=n;j++)
            add(a[j*prim[i]],a[j]);
}
inline void work(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prim[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(prim[j]*i>n)break;
            vis[prim[j]*i]=1;
            if(i%prim[j]==0)break;
        }
    }
}
int main()
{
    work(100000);
    int T=read();
    while(T--)
    {
        int A=read(),B=read(),C=read();
        n=max(A,max(B,C));
        for(int i=1;i<=n;i++)
        {
            a[i]=A/i;
            b[i]=B/i;
            c[i]=C/i;
            d[i]=e[i]=f[i]=(i==1);
        }
        F(e,n);
        F(f,n);
        G(c,n);
        int ans=0;
        for(int i=1;i<=n;i++)//枚举gcd 
        {
            int m=n/i;//[n/d]
            for(int j=1;j<=m;j++)
            {
                p[j]=e[j*i];//pj=f(E)(jd)
                q[j]=f[j*i];//qj=f(F)(jd)
                r[j]=c[j*i];//ri=g(C)(id)
                s[j]=a[j*i];//si=Aid
                t[j]=b[j*i];//ti=Bid
                w[j]=d[j*i];//wi=Did
            }
            F(w,m);
            for(int x=1;x*x<=m;x++)//枚举x 
            {
                fill(u+1,u+1+m,0);
                 fill(v+1,v+1+m,0);
                for(int j=x;j<=m;j+=x)
                {
                    u[j]=s[j];
                    v[j]=t[j];
                }
                G(u,m);
                G(v,m);
                for(int j=1;j<=m;j++)
                {
                    u[j]=1ll*u[j]*w[j]%mod;
                    v[j]=1ll*v[j]*w[j]%mod;
                }
                H(u,m);
                H(v,m);
                for(int j=1;j<=m;j++)
                {
                    u[j]=1ll*u[j]*t[j]%mod;
                    v[j]=1ll*v[j]*s[j]%mod;
                }
                for(int y=x;x*y<=m;y++)//枚举y 
                {
                    if(__gcd(x,y)==1)
                    {
                        int s1=0,s2=0;
                        for(int j=y;j<=m;j+=y)
                        {
                            add(s1,u[j]);//Tjy[jy<=m]
                            add(s2,v[j]);//Six[ix<=m];
                        }
                        add(ans,1ll*s1*p[x]%mod*q[y]%mod*r[x*y]%mod);
                        if(x!=y)add(ans,1ll*s2*p[y]%mod*q[x]%mod*r[x*y]%mod);
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}