QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178391 | #5503. Euclidean Algorithm | real_sigma_team# | ML | 1ms | 3880kb | C++20 | 1.3kb | 2023-09-13 22:39:53 | 2023-09-13 22:39:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using ll = long long;
const int N = 3e5 + 5;
ll get_len(ll n, ll d) {
ll mx = n / d;
ll mn = (n + 1 + d) / (d + 1);
return max(0ll, mx - mn + 1);
}
vector<ll> gen(ll n) {
vector<ll> res, res2;
for (ll i = 1; i * i <= n; ++i) {
res.push_back(n / i);
res2.push_back(n / (n / i));
}
reverse(all(res));
vector<ll> res3;
merge(all(res), all(res2), back_inserter(res3));
res3.resize(unique(all(res3)) - res3.begin());
return res3;
}
ll f(ll n) {
vector<ll> a = gen(n);
ll ans = 0;
// cout << n << endl;
for (auto i : a) {
// cout << i << ' ' << get_len(n, i) << endl;
ans += i * get_len(n, i);
}
// cout << endl;
return ans;
}
void solve() {
ll n;
cin >> n;
ll ans = 0;
vector<ll> a = gen(n);
for (auto d : a) {
// cout << d << ' ' << get_len(n, d) << endl;
ans += f(d - 1) * get_len(n, d);
}
cout << ans << '\n';
}
int main() {
#ifndef LOCAL
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#else
freopen("input.txt", "r", stdin);
#endif
int t;
cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: -100
Memory Limit Exceeded
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425