【题解】洛谷T48568[提高测试TG4]B.yyy送礼物 线性筛

题目链接

简单推导一下，可得每一项 $n$n 的答案为 $n^2-\sum_{i=1}^n(\left\lfloor\frac{n}{i}\right\rfloor*i)$n2−∑i=1n​(⌊in​⌋∗i)
记数列 $a_n=n^2-\sum_{i=1}^n(\left\lfloor\frac{n}{i}\right\rfloor*i)$an​=n2−∑i=1n​(⌊in​⌋∗i)
$a_{n-1}=(n-1)^2-\sum_{i=1}^{n-1}(\left\lfloor\frac{n-1}{i}\right\rfloor*i)$an−1​=(n−1)2−∑i=1n−1​(⌊in−1​⌋∗i)
做差得递推式 $a_n-a_{n-1}=n-1-\sum_{i=1}^{n-1}\big[(\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\frac{n-1}{i}\right\rfloor)*i\big]$an​−an−1​=n−1−∑i=1n−1​[(⌊in​⌋−⌊in−1​⌋)∗i]
思考一下，发现减去的那一坨就是 $n$n 的因子和减去 $n$n，于是可以线性递推了。
因子和可以线性筛方便求出。
（好像做麻烦了……）

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e7+10;
ll ans[N];
int prime[N/10],p,sum[N];
bool iscomp[N];
int read()
{
	int s=0,t=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
	while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();
	return s*t;
}
int t,n;
ll qpow(ll a,int b)
{
	ll ret=1;
	for(;b;b>>=1)
	{
		if(b&1)ret*=a;
		a*=a;
	}
	return ret;
}
void primetable()
{
	sum[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!iscomp[i])prime[p++]=i,sum[i]=1+i;
		for(int j=0;j<p&&i*prime[j]<N;j++)
		{
			iscomp[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				int tmp=i,f=1;
				while(tmp%prime[j]==0)tmp/=prime[j],f++;
			    sum[i*prime[j]]=sum[tmp]*(qpow(prime[j],f+1)-1)/(prime[j]-1);
			    break;
			}
			sum[i*prime[j]]=sum[i]*sum[prime[j]];
		}
	}
}
int main()
{
	primetable();
	for(int i=2;i<N;i++)
	    ans[i]=0ll+ans[i-1]+i-1-(sum[i]-i);
	t=read();
	while(t--)
	{
		n=read();
		printf("%lld\n",ans[n]);
	}
	return 0;
}

总结

挺好的推公式题。线性筛确实可以轻松解决不少问题。