CF1406E. Deleting Numbers

发表于 | 阅读数

交互，给一堆数$1…n$,$n\leq 10^5$,$q\leq 10^4$

  • A a 返回$a$的倍数的数量
  • B a 返回$a$的倍数的数量，并且删除这些数，不删除$x$。
  • C a 回答答案

$10^5$的质数大概$9500$,$\sqrt{10^5}$的质数$70$。

分$x$

  • 大质数$\leq \sqrt{10^5}$
  • $1$
  • 大质数$\times$一些小质数。

首先我们先把所有$1…\sqrt{10^5}$的质数去掉。

这样只剩下$x,1,大质数$

可以通过$\sum \log_i{n}$大概$170$找到$x=大质数\times 非大质数部分$

然后再去寻找是否有这个大质数。

这里使用类似二分的查找

  • $[mid,r]$部分如果出现大质数倍数数量$>1$，就是第三种情况。
  • 如果经过这波操作，通过$A,1$,$[mid,r]$还有残余，则表示有纯质数，这时候再询问一遍（答案一定在这里）。
  • 否则$[l,mid-1]$继续寻找。

询问次数$9500+70+170\leq 10^4$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int npr[N], pr[N], pcnt;
void Prime_init(int X)
{
    npr[1] = 1;

    for (int i = 1; i <= X; i++)
    {
        if (!npr[i])
            pr[++pcnt] = i;
        for (int j = 1; j <= pcnt && pr[j] * i <= X; j++)
        {
            npr[pr[j] * i] = 1;

            if (i % pr[j] == 0)
            {

                break;
            }
        }
    }
}
int cnt = 0;
int bp[N];
vector<int> sp;
int o, ans;
int Aq(int x)
{
    int ans;
    cout << "A " << x << endl;
    fflush(stdout);
    cin >> ans;
    return ans;
}
int Bq(int x)
{
    int ans;
    cout << "B " << x << endl;
    fflush(stdout);
    cin >> ans;
    return ans;
}

void solve(int l, int r)
{

    if (l > r)
        return;
    int mid = (l + r) >> 1;
    int sum = 0;
    for (int i = mid; i <= r; i++)
    {
        int tmp = Bq(bp[i]);
        sum++;
        if (tmp > 1)
        {
            cout << "C " << ans * bp[i] << endl;
            exit(0);
        }
    }
    int p = Aq(1);

    if (o - p != sum)
    {
        for (int i = mid; i <= r; i++)
        {
            int tmp = Bq(bp[i]);
            if (tmp > 0)
            {
                cout << "C " << ans * bp[i] << endl;
                exit(0);
            }
        }
        exit(0);
    }
    o = p;
    solve(l, mid - 1);
}
int main()
{
    int n;
    cin >> n;

    Prime_init(n);
    for (int i = 1; i <= pcnt; i++)
    {
        if (1ll * pr[i] * pr[i] <= n)
        {
            sp.push_back(pr[i]);
        }
        else
        {
            bp[++cnt] = pr[i];
        }
    }
    for (int x : sp)
    {
        Bq(x);
    }
    o = Aq(1);
    ans = 1;
    for (int x : sp)
    {
        int z = 1;
        for (int c = x; c <= n; c *= x)
        {

            int tmp = Aq(c);
            if (tmp == 1)
            {
                z = c;
            }
            else
                break;
        }
        ans *= z;
    }
    solve(1, cnt);
    cout << "C " << ans << endl;
}