数论题 by Lijinnn

Lijinnn保留本题版权,TonyZhao保留题解版权。

题目大意

多次询问,求

$$\sum\limits_{D=1}^{n} \sum\limits_{d|D} \varphi (d) \sum\limits_{k=1}^{\frac{D}{d}} \varphi(k) \lfloor \frac{D}{dk}\rfloor$$

$\text{询问个数}\leq 10^3 , n \leq 10^7$


用到的公式——欧拉反演:$\sum\limits_{d|n} \varphi(d) = n$

鹅心数论题qwq

首先我们发现$\sum$和$\times$混用所以先从最内部的$\sum$开始分析。

$$\sum\limits_{i=1}^{n} \varphi(i) \times \lfloor \frac{n}{i}\rfloor =\sum\limits_{i=1}^{n} \varphi(i) \sum\limits_{j=1}^{n} [j|i] = \sum\limits_{j=1}^{n} \sum\limits_{d|j} \varphi(d) = \sum\limits_{j=1}^{n}j = \frac{n(n+1)}{2}$$

$\lfloor \frac{n}{i}\rfloor$的真实意义就是$1$~$n$中有多少数是$i$的约数所以可以化成$\sum\limits_{i=1}^{n} \varphi(i) \sum\limits_{j=1}^{n}[j|i]$,之后把$[j|i]$提到前面就是$\sum\limits_{j=1}^{n} \sum\limits_{d|j} \varphi(d) $,之后根据欧拉反演就得到结论。

之后原式就被化为$ans = \sum\limits_{D=1}^{n} \sum\limits_{d|D} \varphi (d) \frac{\frac{n}{d}(\frac{n}{d}+1)}{2}$.

之后我们将$\varphi(d)$拎出来,每个$\varphi(d)$贡献次数就是以它为约数的数的个数,最终得到$ans = \sum\limits_{d=1}^{n} \varphi(d) \sum\limits_{k=1}^{\lfloor\frac{n}{d}\rfloor}\frac{k(k+1)}{2}$.

之后就很简单了:线筛$\varphi()$和$\frac{k(k+1)}{2}$并求前缀和,之后对每个询问分块处理一下,最终答案就是$(\varphi(l)-\varphi(i-1))*F(n/i)$.

#include <cstdio>
#include <algorithm>
using namespace std;
#define R register
#define MO 1000000007
#define LIM 10000000
long long t[LIM+1],phi[LIM+1],prm[LIM+1];
bool v[LIM+1];
void init()
{
    phi[1]=t[1]=1;
    R int cnt=0;
    for(int i=2;i<=LIM;++i)
    {
        t[i]=(t[i-1]+i*(i+1)/2)%MO;
        if(!v[i]) prm[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*prm[j]<=LIM;++j)
        {
            v[i*prm[j]]=true;
            if(i%prm[j]) phi[i*prm[j]]=phi[i]*phi[prm[j]];
            else
            {
                phi[i*prm[j]]=phi[i]*prm[j];
                break;
            }
        }
    }
    for(int i=2;i<=LIM;++i) phi[i]=(phi[i-1]+phi[i])%MO;
}
int main()
{
    init();
    R int T,n;
    R long long ans;
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%d",&n);
        for(int i=1,l;i<=n;i=l+1)l=n/(n/i),ans+=((phi[l]-phi[i-1]+MO)%MO)*t[n/i];
        printf("%lld\n",ans);
    }
    return 0;
}