QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#202504#5503. Euclidean Algorithmdanielkou5855TL 0ms3708kbC++17663b2023-10-06 09:49:302023-10-06 09:49:31

Judging History

This is the latest submission verdict.

  • [2023-10-06 09:49:31]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 3708kb
  • [2023-10-06 09:49:30]
  • Submitted

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: 0ms
memory: 3708kb

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: