QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#914348 | #10075. The Romanian Sieve | Screenwalkers (Hirotaka Yoneda, Masataka Yoneda, Daiki Kodama)# | AC ✓ | 352ms | 3584kb | C++17 | 825b | 2025-02-25 11:08:57 | 2025-02-25 11:08:57 |
Judging History
answer
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
long long harmonic_sum(long long n) {
long long b = int(sqrt(n));
long long ans = 0;
for (int i = 1; i <= b; i++) {
ans += n / i;
}
for (int i = 1; i <= b; i++) {
long long ql = n / (i + 1) + 1;
long long qr = n / i + 1;
long long d = max(qr, b + 1) - max(ql, b + 1);
ans += d * i;
}
return ans;
}
long long harmonic_sum_easy(long long n) {
long long res = 0;
for (long long i = 1; i <= n; i++) {
res += n / i;
}
return res;
}
int main() {
long long n;
cin >> n;
long long l = 0, r = 1076832863131 + 10;
while (r - l > 1) {
long long m = (l + r) / 2;
long long res = harmonic_sum(m);
if (res <= n) {
l = m;
} else {
r = m;
}
}
cout << l << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 22ms
memory: 3456kb
input:
11
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 25ms
memory: 3584kb
input:
2846010382
output:
149946143
result:
ok 1 number(s): "149946143"
Test #3:
score: 0
Accepted
time: 21ms
memory: 3584kb
input:
6182
output:
889
result:
ok 1 number(s): "889"
Test #4:
score: 0
Accepted
time: 19ms
memory: 3584kb
input:
4515
output:
675
result:
ok 1 number(s): "675"
Test #5:
score: 0
Accepted
time: 21ms
memory: 3584kb
input:
6633
output:
945
result:
ok 1 number(s): "945"
Test #6:
score: 0
Accepted
time: 22ms
memory: 3456kb
input:
7013
output:
992
result:
ok 1 number(s): "992"
Test #7:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
7073
output:
1000
result:
ok 1 number(s): "1000"
Test #8:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
1174768
output:
100632
result:
ok 1 number(s): "100632"
Test #9:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
2479099
output:
200523
result:
ok 1 number(s): "200523"
Test #10:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
6647755
output:
500651
result:
ok 1 number(s): "500651"
Test #11:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
10516193
output:
767321
result:
ok 1 number(s): "767321"
Test #12:
score: 0
Accepted
time: 22ms
memory: 3456kb
input:
12214430
output:
882249
result:
ok 1 number(s): "882249"
Test #13:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
13969267
output:
999952
result:
ok 1 number(s): "999952"
Test #14:
score: 0
Accepted
time: 21ms
memory: 3584kb
input:
13970037
output:
1000000
result:
ok 1 number(s): "1000000"
Test #15:
score: 0
Accepted
time: 27ms
memory: 3456kb
input:
14015182144
output:
683749676
result:
ok 1 number(s): "683749676"
Test #16:
score: 0
Accepted
time: 26ms
memory: 3584kb
input:
6913981022
output:
348762361
result:
ok 1 number(s): "348762361"
Test #17:
score: 0
Accepted
time: 28ms
memory: 3584kb
input:
15306299347
output:
743689734
result:
ok 1 number(s): "743689734"
Test #18:
score: 0
Accepted
time: 29ms
memory: 3584kb
input:
20877029943
output:
999969499
result:
ok 1 number(s): "999969499"
Test #19:
score: 0
Accepted
time: 30ms
memory: 3584kb
input:
20877697664
output:
1000000000
result:
ok 1 number(s): "1000000000"
Test #20:
score: 0
Accepted
time: 343ms
memory: 3584kb
input:
27785452448923
output:
999999999999
result:
ok 1 number(s): "999999999999"
Test #21:
score: 0
Accepted
time: 324ms
memory: 3584kb
input:
24910761437138
output:
899953929599
result:
ok 1 number(s): "899953929599"
Test #22:
score: 0
Accepted
time: 288ms
memory: 3584kb
input:
18986833745689
output:
692495249599
result:
ok 1 number(s): "692495249599"
Test #23:
score: 0
Accepted
time: 307ms
memory: 3584kb
input:
22048489253712
output:
799952459599
result:
ok 1 number(s): "799952459599"
Test #24:
score: 0
Accepted
time: 295ms
memory: 3584kb
input:
20185303532115
output:
734623956734
result:
ok 1 number(s): "734623956734"
Test #25:
score: 0
Accepted
time: 343ms
memory: 3584kb
input:
27785452449093
output:
1000000000000
result:
ok 1 number(s): "1000000000000"
Test #26:
score: 0
Accepted
time: 21ms
memory: 3584kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 352ms
memory: 3584kb
input:
30000000000000
output:
1076832863131
result:
ok 1 number(s): "1076832863131"
Test #28:
score: 0
Accepted
time: 236ms
memory: 3584kb
input:
12861657076598
output:
475612531234
result:
ok 1 number(s): "475612531234"