解析

打表發現1e5以內的質因子是9592個
就是它沒錯了

容易想到枚舉因子判斷答案是否異常來判斷是否包含該質因子
但是這個方法在最小質因子處是不奏效的

那么如何找到最小的質因子呢？
考慮把所有的質因子分成$\sqrt{m}$塊
然后每掃完一塊，問一下 $(A,1)$
如果異常，那么最小質因子就在這塊里
暴力掃一遍找出來即可

代碼

#include<bits/stdc++.h> using namespace std; const int N=3e5+100; const int mod=1e9+7; double eps=1e-10; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; }int n,m;int vis[N]; ll p[N],tot; int sum,w; int ans(1); bool jd; int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();sum=n;for(int i=2;i<=n;i++){if(vis[i]) continue;vis[i]=1;p[++tot]=i;for(int j=i+i;j<=n;j+=i) vis[j]=1;}printf("tot=%d\n",tot);w=floor(sqrt(tot));memset(vis,0,sizeof(vis));for(int i=1;i<=tot;i++){//if(ans*p[i]>n) break;int now(0);for(int j=p[i];j<=n;j+=p[i]){if(vis[j]) continue;vis[j]=1;now++;sum--;}printf("B %d\n",p[i]);//fflush(stdout);int x=read();if(x!=now){ans*=p[i];ll o=p[i]*p[i];while(o<=n){printf("A %lld\n",o);//fflush(stdout);x=read();if(!x) break;ans*=p[i];o*=p[i];}}if(!jd&&(i%w==0||i==tot)){printf("A 1\n");//fflush(stdout);x=read();if(x==sum) continue;for(int j=(i-1)/w*w+1;j<=i;j++){printf("A %d\n",p[j]);//fflush(stdout);x=read();if(x){jd=1;ans*=p[j];ll o=p[j]*p[j];while(o<=n){printf("A %lld\n",o);//fflush(stdout);x=read();if(!x) break;ans*=p[j];o*=p[j];}break;}}}}printf("C %d\n",ans);fflush(stdout);return 0; } /* 2 3 7 4 9 9 1 2 8 3 1 4 2 4 */

總結

以上是生活随笔為你收集整理的CF1406E:Deleting Numbers（构造、根号分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。