# Участник:Kozub/Find The Number

Перейти к: навигация, поиск

Ссылка на задачу на spoj.com: https://www.spoj.com/problems/IAPCR2D/ С++(компилятор gcc 8.3)

```#include<iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>

namespace mp = boost::multiprecision;

int main(){

//PRECOMPUTING
int j;
int val;
bool not_prime;
int max_n= 112;
mp::int1024_t lst[max_n] ;

int primes[max_n];
int primes_num[max_n];
int n_primes = 0;

primes[0] = 2;
primes_num[0] = 1;

lst[0] = 1;
lst[1] = 1;
lst[2] = 2;

mp::int1024_t deviders = 2;

for(int i=3;i<=max_n;i++){
val = i;
not_prime = false;
j = 0;
while(j <= n_primes  && primes[j] <= val){

if (val % primes[j] == 0){
val = val / primes[j];
not_prime = true;

primes_num[j]+=1;
deviders = deviders*mp::int1024_t(primes_num[j]+1)/mp::int1024_t(primes_num[j]);

}
else{
++j;
}

}

if (!not_prime){
n_primes +=1;
primes[n_primes] = val;
primes_num[n_primes] = 1;
deviders*=2;
}

lst[i]= deviders;
}

//BINARY SEARCHING
int T;
mp::int1024_t X;
std::cin>>T;
for(int i =0;i<T;i++){
std::cin>>X;
int f = std::upper_bound(lst, lst+max_n, X) - lst;
if (f>=max_n || lst[f-1] != X){
std::cout<<"nai\n";
}
else{
std::cout<<f-1<<'\n';
}
}

return 0;
}

```