Java教程

NOIP模拟47:Prime

本文主要是介绍NOIP模拟47:Prime，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

  线性筛裸题。
  首先要记住一个结论：

对于一个数\(n\)，不大于他的素数不超过\(\sqrt{n}\)

  然后就直接算出\([2,min(k,\sqrt{R})]\)范围内的素数，将他们在\([L,R]\)范围内的倍数标记，最后没有标记的就是“类素数”。
  直接异或没被标记的数即可。
  

Code 
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
	#define rr register
	typedef long long ll;
	const int N=1e7+4;
	int cnt;
	ll l,r,k;
	ll ans;
	ll read()
	{
		rr ll x_read=0,y_read=1;
		rr char c_read=getchar();
		while(c_read<'0'||c_read>'9')
		{
			if(c_read=='-') y_read=-1;
			c_read=getchar();
		}
		while(c_read<='9'&&c_read>='0')
		{
			x_read=(x_read<<3)+(x_read<<1)+(c_read^48);
			c_read=getchar();
		}
		return x_read*y_read;
	}
	ll prime[N];
	bool is_not_prime[N];
	bool no[N];
	void pre()
	{
		ll up=sqrt(r)+1;
		for(int i=2;i<=min(k,up);i++)
		{
			if(!is_not_prime[i]) prime[++cnt]=i;
			for(int j=1;j<=cnt&&prime[j]*i<=min(k,up);j++)
			{
				is_not_prime[i*prime[j]]=1;
				if(i%prime[j]==0) break;
			}
		}
	}
};
using namespace STD;
int main()
{
	l=read(),r=read(),k=read();
	pre();
	for(int i=1;i<=cnt;i++)
		for(ll j=max(2ll,l/prime[i]);j*prime[i]<=r;j++)
		{
			ll temp=j*prime[i]-l;
			if(temp>=0)
				no[temp]=1;
		}
	for(int i=0;i<=(r-l);i++)
		if(!no[i])
			ans^=(l+i);
	printf("%lld\n",ans);
}

  
  时间复杂度\(O((r-l)*log(logR))\)
  标记倍数的这一步好像叫“埃氏筛法”，复杂度主要在这里，就是\(O((r-l)*log(logR))\)。
  严格的复杂度是\(O(n+(r-l)*log(logR))\)。\(n\)是线性筛。

这篇关于NOIP模拟47:Prime的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航