用心感受（三）

watersail / 2024-08-07 / 原文

杜教筛要预处理+记忆化才拥有正确的复杂度

点击查看代码

#include <bits/stdc++.h>
using namespace std;
unordered_map<int,long long>q1,q2;
int v[10000005],prime[1000005],m;
int x1[10000005],x2[10000005],S1[10000005];
long long S2[10000005];
long long n,a;
long long s1(int n)
{
	if(n<=10000000)
	{
		return S1[n];
	}
	if(q1.find(n)!=q1.end())
	{
		return q1[n];
	}
	long long sum=1;
	long long l=2,r=0;
	while(l<=n)
	{
		r=n/(n/l);
		sum-=(s1(n/l)*(r-l+1));
		l=r+1;
	}
	return q1[n]=sum;
}
long long s2(int n)
{
	if(n<=10000000)
	{
		return S2[n];
	}
	if(q2.find(n)!=q2.end())
	{
		return q2[n];
	}
	long long sum=1;
	long long l=2,r=0;
	while(l<=n)
	{
		r=n/(n/l);
		sum-=(s2(n/l)*(l+r)*(r-l+1)/2);
		l=r+1;
	}
	return q2[n]=sum;
}
long long s3(int n)
{
	long long sum=0;
	long long l=1,r=0;
	while(l<=n&&l<=a)
	{
		r=a/(a/l);
		if(r>n)
		{
			r=n;
		}
		sum+=(a/l*(s2(r)-s2(l-1)));
		l=r+1;
	}
	return sum;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	x1[1]=x2[1]=S1[1]=S2[1]=1;
	for(int i=2;i<=10000000;i++)
	{
		if(v[i]==0)
		{
			v[i]=i;
			prime[++m]=i;
			x1[i]=-1;
			x2[i]=-i;
		}
		S1[i]=S1[i-1]+x1[i];
		S2[i]=S2[i-1]+x2[i];
		for(int j=1;j<=m;j++)
		{
			if(i*prime[j]>10000000||prime[j]>v[i])
			{
				break;
			}
			v[i*prime[j]]=prime[j];
			if(x1[i]==0||prime[j]==v[i])
			{
				x1[i*prime[j]]=0;
				x2[i*prime[j]]=0;
			}
			else
			{
				x1[i*prime[j]]=x1[i]*(-1);
				x2[i*prime[j]]=x1[i*prime[j]]*(i*prime[j]);
			}
		}
	}
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>a;
		cout<<a*s1(n)-s3(n)<<endl;
	}
	return 0;
}