QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136357#5503. Euclidean Algorithmdanielkou5855TL 1ms3472kbC++14663b2023-08-08 04:06:372023-08-08 04:06:38

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-08 04:06:38]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3472kb
  • [2023-08-08 04:06:37]
  • 提交

answer

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#define ll long long

using namespace std;

void solve() {
	ll N; cin >> N;

	ll ct = 0;

	for (ll r = 1; r <= N; r = N / (N / r) + 1) {
		// do something with N / r
		ll fixed = N / r;
		ll M = fixed - 1;

		ll last = N / (N / r);
		// cout << r << " " << last << "\n";

		for (ll p = 1; p <= M; p++) {
			ct += (last - r + 1) * (M / p);
		}

		// cout << ct << "\n";
	}

	cout << ct << "\n";
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);

	int T; cin >> T;

	while (T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3472kb

input:

3
2
5
14

output:

1
9
62

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

3
29107867360
65171672278
41641960535

output:


result: