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
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include "dzilib.h"
using namespace std;

const int N = 1'000'005;
const int N2 = 2 * N;


void check(vector<int> &cnt) {
    vector<int> candidates;
    candidates.reserve(N);
    for (int i = 1; i < N; i++) {
        candidates.push_back(i);
    }
    
    for (int y = 0; ; y++) {
        int n = Ask(y);

        vector<int> matched;
        for (int cand : candidates) {
            if (cnt[cand + y] == n) {
                matched.push_back(cand);
            }
        }
        candidates.clear();
        candidates.insert(candidates.end(), matched.begin(), matched.end());
        if (candidates.size() == 1) {
            Answer(candidates[0]);
            break;
        }
    }
}

int main() {
    vector<int> v(N2);
    for (int i = 2; i * i <= N2; i++) {
        if (!v[i]) {
            for (int k = i * i; k <= N2; k += i) {
                if (!v[k]) {
                    v[k] = i;
                }
            }            
        }
    }

    vector<int> cnt(N2, 1);
    for (int i = 1; i < N2; i++) {
        int x = i;
        map<int, int> m;
        if (v[x] == 0) {
            m[x]++;
        }
        else {
            while (v[x] > 0) {
                m[v[x]]++;
                x /= v[x];
            }
            m[x]++;
        }
        for (auto &e : m) {
            cnt[i] *= (e.second + 1);
        }
    }
    cnt[1] = 1;
    
    map<int, vector<int>> divs;
    for (int i = 1; i < N2; i++) {
        divs[cnt[i]].push_back(i);
    }
    
    long long t = GetT();
    long long n = GetN();
    long long q = GetQ();
    long long c = GetC();

    while (t--) {
        check(cnt);
    }

    return 0;
}