Java教程

题解 Prime

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

传送门

考场上魔改了一下线性筛，觉得要筛到 \(\frac{R}{2}\) 就没让它跑
其实正解就是这样，只不过由于接下来类似埃氏筛的过程只要筛到根号就行了

  • 线性筛有的时候其实并不需要筛到 \(\frac{n}{2}\)，如果接下来需要枚举倍数，注意可能只需要枚举到根号就行了

发现 \(R\) 的范围很大，但 \(R-L\) 的范围有限
而 \(L\) 的范围只有 \(1e7\)，可以筛出质数来，再用类似埃氏筛的方法筛掉 \([L, R]\) 内的类质数
然后枚举一遍统计个数就好了

Code: 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 10000010
#define ll long long 
#define reg register int
#define rll register long long 
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline ll read() {
	ll ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

ll l, r, k;
int pri[N], pcnt, ans;
bool npri[N];

namespace force{
	ll ans;
	void solve() {
		for (ll i=l; i<=r; ++i) {
			for (ll j=2; j<=min(i-1, k); ++j)
				if (!(i%j)) goto jump;
			//printf("%lld,%lld\n", i, (ans^=i));
			//printf("%lld ", i);
			ans^=i;
			jump: ;
		}
		//printf("\n");
		printf("%lld\n", ans);
		exit(0);
	}
}

namespace task1{
	void solve() {
		for (reg i=2,limr=r,limk=k; i<=limr; ++i) {
			if (i<=limk && !npri[i]) pri[++pcnt]=i;
			for (reg j=1; j<=pcnt&&1ll*i*pri[j]<=r; ++j) {
				npri[i*pri[j]]=1;
				if (!(i%pri[j])) break;
			}
		}
		for (reg i=l,limr=r; i<=limr; ++i)
			if (!npri[i]) ans^=i; //, cout<<i<<' '; cout<<endl;
		printf("%d\n", ans);
		exit(0);
	}
}

namespace task2{
	void solve() {
		ll ans=0;
		for (rll i=l; i<=r; ++i) ans^=i;
		printf("%lld\n", ans);
		exit(0);
	}
}

namespace task3{
	bool nspr[N];
	void solve() {
		for (reg i=2,lim=min((ll)(sqrt(r)),k); i<=lim; ++i) {
			if (!npri[i]) pri[++pcnt]=i;
			for (reg j=1; j<=pcnt&&1ll*i*pri[j]<=lim; ++j) {
				npri[i*pri[j]]=1;
				if (!(i%pri[j])) break;
			}
		}
		for (reg i=1; i<=pcnt; ++i) {
			//cout<<"i: "<<i<<' '<<pri[i]<<endl;
			for (rll j=max((l-1)/pri[i]+1,2ll),lim=r/pri[i]; j<=lim; ++j) {
				//cout<<j*pri[i]<<' '<<j*pri[i]-l<<endl;
				nspr[j*pri[i]-l]=1; //, cout<<j*pri[i]<<endl;
			}
		}
		ll ans=0;
		//for (int i=0; i<=100; ++i) cout<<nspr[i]<<' '; cout<<endl;
		for (reg i=0,lim=r-l+1; i<lim; ++i) if (!nspr[i]) ans^=(l+i);
		printf("%lld\n", ans);
		exit(0);
	}
}

signed main()
{
	l=read(); r=read(); k=read();
	//force::solve();
	if (k==1) task2::solve();
	else if (r<=1000) force::solve();
	else if (r<=(ll)(1e7)) task1::solve();
	else task3::solve();
	
	return 0;
}
这篇关于题解 Prime的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航