题解 CF1406E 【Deleting Numbers】

钓鱼王子 · 2020-09-13 22:49:04 · 题解

出题人题解：

如果我们知道 x 的所有质因数，可以用暴力枚举幂次找到答案。

可以对于每一个质数 p 做一次询问 B~p，若得到答案和没有 x 的答案不同，则说明 x 有 p 这一个质因子。

通过这样的方法，我们可以找到除最小质因子以外的质因子。

对于最小的质因子，可以采用分块，令 m 为质数个数，每隔 \sqrt m 次做一次 A~1 询问，检查最小质因子是否在区间里，如果在，则扫描一遍区间对于每一个质因数找一次 A~p，即可得到所有质因数。

总操作次数：m+2\sqrt m+\log n，时间复杂度：O(n\log n)。

自我评价：是一道很不错的题目！

#include<bits/stdc++.h>
#define re register
#define int long long
using namespace std;
bool vis[100002];
int pri[100002],tot,n,x,sum,ans,ia;
signed main(){
    srand(19260817); 
    scanf("%lld",&n);
    for(re int i=2; i<=n; ++i) {
        if(!vis[i]) {
            pri[++tot]=i;
            if(i<=sqrt(n))
            for(re int j=i*i; j<=n; j+=i)vis[j]=1;
            }
    }
    memset(vis,0,sizeof(vis));
    re int k=sqrt(tot);sum=n;ans=1;
    for(re int i=1;i<=tot;++i){
        if(i>=k&&ans*pri[i-k+1]>n)break;
        printf("B %lld",pri[i]);cout<<endl;
        re int num=0;
        for(re int j=pri[i];j<=n;j+=pri[i]){
            if(!vis[j]){
                ++num;--sum;
                vis[j]=1;
            }
        }
        scanf("%lld",&x);
        if(x!=num){
            for(re int kk=pri[i];kk<=n;kk*=pri[i]){
                    printf("A %lld",kk);cout<<endl;
                    scanf("%lld",&x);
                    if(x)ans*=pri[i];
                    else break;
            }
        }
        if((i==tot||i%k==0)&&!ia){
            printf("A 1");cout<<endl;
            scanf("%lld",&x);
            if(x!=sum){
                for(re int j=i-k+1;j<=i;++j){
                    for(re int kk=pri[j];kk<=n;kk*=pri[j]){
                        printf("A %lld",kk);cout<<endl;
                        scanf("%lld",&x);
                        if(x)ans*=pri[j],ia=1;
                        else break;
                    }
                    if(ia)break;
                }
            }
        }
    }
    printf("C %lld",ans);cout<<endl;
}