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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#include <cstdlib>
#include <cstdint>

#include <vector>
#include <algorithm>

#include "dzilib.h"

std::vector<uint64_t> genprimes() {
    uint64_t primorial = 2;
    std::vector<uint64_t> ret;
    ret.push_back(2);

    // We will need a very small number of primes, so a dumb algo is OK
    for (uint64_t i = 3; ret.size() < 30; i += 2) {
        bool is_prime = true;
        for (uint64_t p : ret) {
            if (p * p > i) {
                break;
            }
            if (i % p == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            ret.push_back(i);
            primorial *= i;
        }
    }

    return ret;
}

void solve(std::vector<uint64_t> primes, const uint64_t n, const uint64_t c) {
    // printf("test START\n");
    // Handle the special case here: is it 1?
    if (Ask(0) == 1) {
        Answer(1);
        return;
    }

    // const uint64_t largest_prime = primes.back();

    // Other numbers will have at least 2 divisors

    std::vector<std::vector<bool>> crossing_game;
    std::vector<int> per_prime_remaining;
    for (uint64_t p : primes) {
        crossing_game.emplace_back();
        crossing_game.back().resize(p, false);
        per_prime_remaining.push_back(p);
    }

    // std::vector<uint64_t> completed_primes;

    uint64_t completed_primes_product = 1;
    uint64_t offset = 0;
    while (completed_primes_product <= n) {
        // printf("%llu %llu\n", offset, completed_primes_product);
        offset += completed_primes_product;

        if (offset > c) {
            // Not sure this helps :(
            // printf("Rewinding! before it was %llu\n", offset);
            offset %= completed_primes_product;
        }

        bool worth_checking_any = false;
        for (int i = 0; i < primes.size(); i++) {
            if (!crossing_game[i][offset % primes[i]]) {
                worth_checking_any = true;
                break;
            }
        }

        if (worth_checking_any && Ask(offset) == 2) {
            // This is a prime
            // For all our primes, disqualify it as a number divisible by that prime
            // printf("Product: %lld\n", completed_primes_product);
            // printf("Limit: %lld\n", c / largest_prime);
            // printf("c: %lld\n", c);
            // printf("off: %lld\n", offset);
            for (int i = 0; i < primes.size(); i++) {
                if (!crossing_game[i][offset % primes[i]]) {
                    crossing_game[i][offset % primes[i]] = true;
                    // printf("prime %lld down to %d (rem %lld)\n", primes[i], per_prime_remaining[i] - 1, offset % primes[i]);
                    if (--per_prime_remaining[i] == 1) {
                        // We can now adjust the offset so that we will never encounter a number divisible by it again 
                        uint64_t target_remainder = std::distance(crossing_game[i].begin(), std::find(crossing_game[i].begin(), crossing_game[i].end(), false));
                        target_remainder = (target_remainder + 1) % primes[i];

                        // The current offset has correct reminders wrt completed primes.
                        // We need to adjust it so that it also has the correct reminder 1 wrt to the new prime.
                        // Primes are small, so don't bother with the modular inverse
                        while (offset % primes[i] != target_remainder) {
                            offset += completed_primes_product;
                        }
                        // printf(" Offset is now %lld\n", offset);
                        // printf(" Selected prime %lld\n", primes[i]);
                        // printf(" Increasing completed primes product from %lld to %lld\n", completed_primes_product, completed_primes_product * primes[i]);
                        completed_primes_product *= primes[i];

                        // DEBUG
                        // DEBUG
                        // completed_primes.push_back(primes[i]);
                        // for (uint64_t p : completed_primes) {
                        //     printf("  %lld / %lld == %lld\n", offset, p, offset % p);
                        // }

                        // Not sure why needed
                        offset %= completed_primes_product;

                        // No longer needed to check this prime out explicitly
                        primes.erase(primes.begin() + i);
                        crossing_game.erase(crossing_game.begin() + i);
                        per_prime_remaining.erase(per_prime_remaining.begin() + i);

                        // DEBUG
                        // for (uint64_t p : primes) {
                        //     printf("  remaining: %lld\n", p);
                        // }

                        break;
                    }
                }
            }
        }
    }

    // Now, we know that `hidden number` + `offset` == `1` modulo `completed_primes_product`.
    // completed_primes_product is larger than the looked for number, so we can determine
    // uniquely which number that is.
    const uint64_t answer = (completed_primes_product + 1 - offset) % completed_primes_product;
    Answer(answer);
}

int main() {
    const int t = GetT();
    const uint64_t n = GetN();
    const uint64_t c = GetC();
    const std::vector<uint64_t> primes = genprimes();
    for (int i = 0; i < t; i++) {
        solve(primes, n, c);
    }

    return 0;
}