QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136357 | #5503. Euclidean Algorithm | danielkou5855 | TL | 1ms | 3472kb | C++14 | 663b | 2023-08-08 04:06:37 | 2023-08-08 04:06:38 |
Judging History
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