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

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

Ссылка на задачу на 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;
}