Tìm số có n ước

Xem PDF
Tác giả:
jumptozero
Dạng bài
Điểm: 1500 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên dương \(n\). Gọi \(s\) là số nguyên dương nhỏ nhất có chính xác \(n\) ước (ở đây ta chỉ tính ước dương).

Yêu cầu: Cho số nguyên dương \(n\). In ra \(s\) (Biết rằng: Đề ra đảm bảo \(s\le 10^{18}\))

Input

  • Một dòng duy nhất chứa số nguyên \(n(1\le n\le 1000)\)

Output

  • In ra \(s\) cần tìm

Example

Test 1

Input 
2
Output 
2
Note

Giải thích: Đáp án là \(2\) vì \(2\) là số nguyên dương nhỏ nhất có chính xác \(2\) ước (dương).

Bình luận


  • 0
    pa_ldk    8:52 a.m. 5 Tháng 5, 2024

    include <bits/stdc++.h>

    define ll long long

    using namespace std;

    vector<ll> prime;

    void sieve(ll maxn) {
    vector<ll> check(maxn+1, true);
    for (ll i=2; ii<=maxn; ++i) {
    if (check[i]) {
    for (ll j=i    i; j<=maxn; j+=i) {
    check[j] = false;
    }
    }
    }
    for (ll i=2; i<=maxn; ++i) {
    if (check[i]) prime.push_back(i);
    }
    }

    ll res = LLONG_MAX, n;
    void Try(ll i, ll now, ll cnt) {
    for (ll j=1; now * prime[i] <= res; ++j) {
    now *= prime[i];
    if (now < 0) return;
    if (cnt * (j+1) >= n) {
    if (cnt * (j+1) == n) res = min(res, now);
    else return;
    } else Try(i+1, now, cnt * (j+1));
    }
    }

    int main() {

    cin >> n;
sieve(100);

Try(0, 1, 1);

cout << res;

    }
    code c++

      • 9 bình luận nữa