Luogu P3708 koishi的数学题

题意

给定整数 (n)，设 (f(x)=sumlimits_{i=1}^{n}xmod i)，对于 (1leq ileq n) 求 (f(i))。

( exttt{Data Range:}1leq nleq 10^6)

题解

做完这题之后看了一下题解区，都写的啥啊，来写篇思路清晰点的。

考虑推下式子：

[sumlimits_{i=0}^{n}xmod i=nx-sumlimits_{i=1}^{n}ileftlfloorfrac{x}{i} ight floor ]

接下来考虑差分：

[sumlimits_{i=1}^{n}ileft(leftlfloorfrac{x}{i} ight floor-leftlfloorfrac{x-1}{i} ight floor ight)=sumlimits_{i=1}^{n}i[imid x]=sigma(x) ]

所以

[sumlimits_{i=0}^{n}xmod i=nx-sumlimits_{i=1}^{x}sigma(i) ]

线性筛出 (sigma(i)) 的前缀和即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=1e6+51;
ll n,ptot;
li cur;
ll np[MAXN],prime[MAXN],low[MAXN];
li sum[MAXN],sigma[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void sieve(ll limit)
{
    np[1]=low[1]=sum[1]=sigma[1]=1;
    for(register int i=2;i<=limit;i++)
    {
        if(!np[i])
        {
            prime[++ptot]=i,low[i]=i,sum[i]=sigma[i]=i+1;
        }
        for(register int j=1;i*prime[j]<=limit;j++)
        {
            np[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                low[i*prime[j]]=low[i]*prime[j];
                sum[i*prime[j]]=sum[i]+low[i*prime[j]];
                sigma[i*prime[j]]=sigma[i]/sum[i]*sum[i*prime[j]];
                break;
            }
            low[i*prime[j]]=prime[j],sum[i*prime[j]]=prime[j]+1;
            sigma[i*prime[j]]=sigma[i]*sigma[prime[j]];
        }
    }
}
int main()
{
    sieve(n=read());
    for(register int i=1;i<=n;i++)
    {
        cur+=sigma[i],printf("%lld ",(li)i*n-cur);
    }
}