题解CF1406E Deleting Numbers

CF1406E Deleting Numbers

交互题

考虑枚举所有n以内的质数,用一次查询B,再进行查询A,若返回1,则说明a为当前枚举的质数的倍数

考虑到唯一分解定理,再不断枚举当前质数的幂次方,进行查询A,最终可以确定a.

很明显,这样的操作次数是质因子数+幂次方数的,而100000内的质数有9600多个,所以会超出题目的限制

可以按两种情况考虑

1.$x\le\sqrt{n}$ 直接暴力枚举

2.$x>\sqrt{n}$,这时假设已经枚举完了所有的小质数,得到的答案为ans

A:ans>1,这时集合内就只剩大于 $\sqrt{n}$ 的质数了,所以直接对每一个质数*ans进行查询A,若返回1,则为答案

B:ans=1,说明答案为一个质数,但不可能直接枚举每一个质数,所以可以对每一个质数进行分块处理,分成 $\sqrt{n}$ 块,首先

对每一块中的所有数进行一次查询B,再对1进行一次查询A,比较是否有减少的数,若有,就直接在块中暴力查询即可

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;

bool st[N];
int prime[N], tot;

void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
            prime[++tot] = i;
        for (int j = 1; i * prime[j] <= n; j++)
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

int ask_A(int x)
{
    printf("A %d\n", x);
    fflush(stdout);scanf("%d", &x);
    return x;
}

int ask_B(int x)
{
    printf("B %d\n", x);
    fflush(stdout);scanf("%d", &x);
    return x;
}

int main()
{ 
    int n, x, ans = 1, t = 0;
    scanf("%d", &n);
    init(n);
    int sn = sqrt(n);
    for (int i = 1; prime[i] <= sn && i <= tot; i++)
    { 
        x = ask_B(prime[i]);
        if (!x) continue;
        int p = prime[i];
        if (!ask_A(p))
            continue;
        while (p * prime[i] <= n && ask_A(p * prime[i]))
            p *= prime[i];
        ans *= p;
        t = i;
    }
    if (ans > 1)
    {
        for (int i = t + 1; (ll)prime[i] * ans <= n; i++)
        {
            if (ask_A(ans * prime[i]))
            {
                printf("C %d\n", ans * prime[i]);
                fflush(stdout);
                return 0;
            }
        }
    }
    else
    {
        int len = sqrt(tot);
        for (int l = t + 1; l <= tot; l += len)
        {
            int r = min(tot, l + len - 1);
            for (int i = l; i <= r; i++)
                ask_B(prime[i]);
            x = ask_A(1);
            if (x > tot - r + 1)
            {
                for (int i = l; i <= r; i++)
                {
                    if (ask_A(prime[i]))
                    {
                        printf("C %d", prime[i]);
                        fflush(stdout);
                        return 0;
                    }  
                }
            }
        }
    }
    printf("C %d\n", ans);
    fflush(stdout);
    return 0;
}