QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178391#5503. Euclidean Algorithmreal_sigma_team#ML 1ms3880kbC++201.3kb2023-09-13 22:39:532023-09-13 22:39:54

Judging History

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

  • [2023-09-13 22:39:54]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3880kb
  • [2023-09-13 22:39:53]
  • 提交

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

result: