Tìm số có n ước
Xem PDF
Đ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
2Output
2Note
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
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=ii; 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() {
}
code c++
output ra 2 đúng rồi mà sao sai hết vậy?
bài này chắc phân tích ngtố 😕
.
SOS
Bài này đệ quy được vì giới hạn của s chỉ bé hơn 10^18 hay 2^64 trong trường hợp chọn toàn 2 (số càng lớn thì số các trường hợp cần xét sẽ càng giảm đi)
.
100th problem:D
bài này quay lui được nè !
bài này có sol ko ạ