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
// Przykładowe niepoprawne rozwiązanie do zadania Dzielniki.
#include "dzilib.h"
#include <bits/stdc++.h>
using namespace std;

vector<int>primes;
int sito[1000110];

long long f(long long x){
	if(x==1)return 1;
	vector<int>pom;
	while(x!=1 && (pom.size()==0 || sito[x]==pom.back())){
		pom.push_back(sito[x]);
		x/=sito[x];
	}
	return f(x)*(pom.size()+1);
}

struct node{
	int war;
	map<int,int>graf;
};
vector<node>trie;
long long policz[1000110];
int main() {
	for(long long i=2;i<=1000100;i++)
		if(!sito[i]){
			sito[i] = i;
			primes.push_back(i);
			for(long long j=i*i;j<=1000100;j+=i)
				if(sito[j]==0)
					sito[j] = i;
		}
	int t = GetT();
	int q = GetQ();
	long long c = GetC();
	long long n = GetN();
	if(n<=1000000){
		trie.push_back({});
		int i, j;
		for(i=1;i<=n+10;i++)
			policz[i] = f(i);
		for(i=1;i<=n;i++){
			int it = 0;
			for(j=0;j<10;j++){
//				if(i==1000)printf("%d\n", it);
				int pom = policz[i+j];
				if(trie[it].graf[pom]!=0){
					it = trie[it].graf[pom];
				}
				else{
					trie[it].graf[pom] = trie.size();
					it = trie.size();
					trie.push_back({});
				}
			}
			trie[it].war = i;
		}
		while(t--){
			int it = 0;
			int i = 0;
			while(trie[it].graf.size()){
//				printf("%d %d\n", it, i);
				int pom = Ask(i);
				it = trie[it].graf[pom];
				i++;
			}
			Answer(trie[it].war);
		}
		
		return 0;
	}
}