QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#914348#10075. The Romanian SieveScreenwalkers (Hirotaka Yoneda, Masataka Yoneda, Daiki Kodama)#AC ✓352ms3584kbC++17825b2025-02-25 11:08:572025-02-25 11:08:57

Judging History

This is the latest submission verdict.

  • [2025-02-25 11:08:57]
  • Judged
  • Verdict: AC
  • Time: 352ms
  • Memory: 3584kb
  • [2025-02-25 11:08:57]
  • Submitted

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"