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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include "dzilib.h"

#define N 1000200ULL

void sieve(char* isnprime, int* primes) { 
    int i, p, j;
    memset(isnprime, 0, N);
    isnprime[0] = 1;
    isnprime[1] = 1;
  
    j = 0;
    for (p = 2; p < N / 2; ++p) { 
        if (isnprime[p] == 0) { 
            for (i = 2 * p; i < N; i += p) 
                isnprime[i] = 1; 
            primes[j++] = p;
        } 
    }
} 
  
int divisors(int k, char* isnprime, int* primes) 
{ 
    if (k == 1) 
        return 1; 

    int ret = 1;
    int i;
    int cnt;
  
    for (i = 0;; i++) { 
        if (primes[i] * primes[i] > k) 
            break; 

        cnt = 1;
        while (k % primes[i] == 0)
        { 
            k = k / primes[i]; 
            cnt = cnt + 1;
        } 
  
        ret *= cnt; 
    } 
  
    if (isnprime[k] == 0)
        ret *= 2; 
  
    return ret;
} 

int main(int argc, char* argv[]) {
    char* isnprime = new char[N];
    int* primes = new int[N];
    int* divs = new int[N];
    int i;

    sieve(isnprime, primes);

    for (i = 1; i < N; ++i) {
        divs[i] = divisors(i, isnprime, primes);
    }

    int q = GetQ();
    int t = GetT();
    q = q / t;
    int* answ = new int[q];

    int ti, qi, di, ai;
    for (ti = 0; ti < t; ++ti) {
        for (qi = 0; qi < q; ++qi) {
            answ[qi] = Ask(qi);
        }
        di = 0;
        ai = 0;
        while (di < N) {
            if (divs[di] == answ[ai]) {
                di++;
                ai++;
                if (ai == q) {
                    break;
                }
            } else if (ai > 0) {
                ai = 0;
            } else {
                di++;
            }
        }
        Answer(di - q);
    }
    return EXIT_SUCCESS;
}