CF1406E Deleting Numbers

做法：

枚举所有小于等于n的素数：

分成两部分:

小于等于sqrt(n)时：

B询问一个素数，然后A询问，如果A询问结果为0，那么全删了，如果A询问结果为1，说明x是这个素数的倍数，按因数分解的素因子逆向枚举这个x。

大于sqrt(n)时：

分块A操作删一个块的素数，超过或者到最后询问一个A 1看看有没有删少了，删少了就在这个块里。
实现1：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pii;
#define mp make_pair
#define fi first
#define se second
#define All(x) (x).begin(),(x).end()
#define Y1 "YES"
#define N1 "NO"
#define ENDL '\n'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
inline ll read(){//not solve LLONG_MIN LMAX=9,223,372,036,854,775,807
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int maxquery=1e4;//最大询问次数
const int PRSIZE=2e5;
int isprime[PRSIZE];
vectorprimelist; //记录素数
vectorprimeval[10000];
int n;
void init(){
	for(int i=2;i<=n;++i){
		isprime[i]=true;
	}
	for(int i=2;i<=n;++i){
		if(isprime[i]){
			int sz=primelist.size();
			primeval[sz].push_back(i);
			for(int j=2;j*iblock;//to solve primelist[query]>n
int main(){
	n=read();
	init();
	int allcnt=n;
	unsigned int querynum=0;
	bool finder=false;
	int i=1;
	for(i=1;iallcnt){
					bool checker=false;
					for(unsigned int iprime=0;iprime


实现2：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pii;
#define mp make_pair
#define fi first
#define se second
#define All(x) (x).begin(),(x).end()
#define Y1 "YES"
#define N1 "NO"
#define ENDL '\n'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
inline ll read(){//not solve LLONG_MIN LMAX=9,223,372,036,854,775,807
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
constexpr int SIZE=1e5+1;
constexpr int PRSIZE=1e4;//cnt=9592
int primelist[PRSIZE],pcnt=0;
bool isprime[SIZE];
int n;
//vectorprimeval[PRSIZE];
void init(){
	for(int i=2;i<=n;++i) isprime[i]=true;
	for(int i=2;i<=n;++i){
		if(isprime[i]==true){
			primelist[pcnt++]=i;
			for(int j=2;j*i<=n;++j)
			isprime[i*j]=false;
		}
	}
}
inline int fpow(int a,int b){
	if(b==0) return 1;
	if(a==0) return 0;
	int ans=1,base=a;
	for(;b>0;b/=2){
		if(b&1)ans*=base;
		base=base*base;
	}
	return ans;
}
constexpr int BLOCKSIZE=98;//sqrt(9592)
int block[BLOCKSIZE],bcnt;
int main(){
	n=read();
	int sq=sqrt(double(n));
	init();
	int ans=1;
	int LLCNT=n;
	for(int i=0;i>answerB;//!=0
			LLCNT-=answerB;
			cout<<"A "<>answerA;
			int factor=1;
			if(answerA!=0){
				LLCNT+=answerA;
				int base=now;
				factor=base;
				for(int j=2;base*now<=n;++j){
					base*=now;
					cout<<"A "<>answerA;
					if(answerA==1)
					factor=base;
					else break;
				}
				ans*=factor;
			}
		}
		else if(ans<=sqrt(n)){
			cout<<"B "<>answerB;
			LLCNT-=answerB;
			if(bcnt==BLOCKSIZE||i==pcnt-1){
				cout<<"A "<<1<>realcnt;
				if(realcnt>LLCNT){
					for(int ib=0;ib>answerA;
						if(answerA==1){
							ans*=block[ib];
							bcnt=0;
							break;
						}
					}
				}
				bcnt=0;
			}
		}
		else break;
	}
	cout<<"C "<


						
							

						
							
							
			算法CodeForces


					
					
					
						相关
						
				
						
			
																
								
										如何实现LRU（最近最少使用）缓存淘汰算法？
									
									
								 

        
								
							
							

																
								
										2021.11.16（各排序算法对比）
									
									
								 

        
								
							
							

																
								
										react dom移动算法
									
									
								 

        
								
							
							

																
								
										算法第四章上机实验报告
									
									
								 

        
								
							
							

																
								
										算法第二章实践报告
									
									
								 

        
								
							
							

																
								
										【莫队算法】
									
									
								 

        
								
							
							

																
								
										算法第四章实践报告
									
									
								 

        
								
							
							

																
								
										关于tarjan算法的一些整理
									
									
								 

        
								
							
							

																
								
										【基础】排序算法学习笔记
									
									
								 

        
								
							
							

																
								
										常用的排序算法介绍和在JAVA的实现（一）
									
									
								 

        
								
							
							

																
								
										数据结构与算法之PHP查找算法（哈希查找）
									
									
								 

        
								
							
							

																
								
										数据结构与算法之PHP查找算法（二分查找）