結果

問題 No.1176 少ない質問
ユーザー Udit GuptaUdit Gupta
提出日時 2020-08-21 22:52:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 360 ms / 1,000 ms
コード長 2,505 bytes
コンパイル時間 1,660 ms
コンパイル使用メモリ 171,572 KB
実行使用メモリ 167,876 KB
最終ジャッジ日時 2024-10-15 06:06:32
合計ジャッジ時間 9,782 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 329 ms
167,744 KB
testcase_01 AC 329 ms
167,664 KB
testcase_02 AC 328 ms
167,744 KB
testcase_03 AC 330 ms
167,620 KB
testcase_04 AC 326 ms
167,740 KB
testcase_05 AC 328 ms
167,616 KB
testcase_06 AC 327 ms
167,876 KB
testcase_07 AC 327 ms
167,744 KB
testcase_08 AC 329 ms
167,744 KB
testcase_09 AC 329 ms
167,744 KB
testcase_10 AC 331 ms
167,748 KB
testcase_11 AC 327 ms
167,744 KB
testcase_12 AC 325 ms
167,740 KB
testcase_13 AC 327 ms
167,744 KB
testcase_14 AC 327 ms
167,748 KB
testcase_15 AC 360 ms
167,740 KB
testcase_16 AC 330 ms
167,616 KB
testcase_17 AC 326 ms
167,748 KB
testcase_18 AC 325 ms
167,744 KB
testcase_19 AC 329 ms
167,616 KB
testcase_20 AC 314 ms
167,744 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//             Author: Udit "luctivud" Gupta @ (https://www.linkedin.com/in/udit-gupta-1b7863135/)                  //


#include <bits/stdc++.h>
#pragma GCC optimize "trapv"

using namespace std;

typedef long long int lld;
typedef unsigned long long int llu;

#define         TESTCASES()    cin >> (T3X0); T353 = T3X0; while(T3X0--)
#define         _input(V3C)    for(auto &V3C_I7 : (V3C)) cin >> (V3C_I7)
#define   mems(A77AY, V4LU)    memset((A77AY), (V4LU), sizeof((A77AY)))
#define    CH3K(I7, E4, S7)    (((S7)<0) ? (I7)>(E4) : (I7)<(E4))
#define   for4(I7,S4,E4,S7)    for(auto I7=(S4); CH3K(I7,E4,S7); (I7)+=(S7))
#define              len(v)    ((int)((v).size()))
#define              all(x)    (x).begin(), (x).end()
#define             rall(x)    (x).rbegin(), (x).rend()
#define             deb1(x)    cout << #x << "=" << (x) << "\n";
#define             deb2(x)    cout << #x << "=" << (x) << " ";





/* This part should be outside the main in global paradigm. */

const long long MAXN = (lld)(1e7) + 1ll; // MAXN Size

vector<long long >isPrime(MAXN , true); // checkIfPrime
vector<long long >prime_numbers; // List of prime numbers
vector<long long >smallest_prime_factor(MAXN); // smallest_prime_factor of a number


void manipulated_seive() {
	isPrime[0] = isPrime[1] = false ;
	
	prime_numbers.push_back(2);
	smallest_prime_factor[2] = 2ll;

	for (long long int i=4; i < MAXN ; i+=2) {
		isPrime[i] = false;
		smallest_prime_factor[i] = 2ll;
	}

	for (long long int i = 3; i < MAXN ; i+=2) {
		if (isPrime[i]) {
			prime_numbers.push_back(i);
			smallest_prime_factor[i] = i;
		}

		for (long long int j = 0; j < (int)prime_numbers.size() && i * prime_numbers[j] < MAXN && prime_numbers[j] <= smallest_prime_factor[i]; j++) {
			isPrime[i * prime_numbers[j]] = false;
			smallest_prime_factor[i * prime_numbers[j]] = prime_numbers[j] ;
		}
	}
}






void solveEachTest(lld T35TC453N = 1) {
    llu a; cin >> a;
	llu ans = a;
	llu idx = 0;
	llu sz = llu(prime_numbers.size());
	llu i = prime_numbers[idx];
	while (idx < sz) {
		llu temp = a;
		llu j = 0llu;
		while (temp) {
			temp /= i;
			j++;
		}
		ans = min(ans, i*j);
		i = prime_numbers[++idx];
	}
	cout << ans;
    cout << "\n"; 

    return;
}


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(10);

/* This should be called inside main. */
	manipulated_seive();
    lld T3X0 = 0, T353 = 1;

    // TESTCASES() 
        solveEachTest(T353 - T3X0);
    return 0;
}
// Random Thought :  null
0