QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #298288 | #5503. Euclidean Algorithm | 0xyz | AC ✓ | 24470ms | 3676kb | C++14 | 466b | 2024-01-05 22:44:58 | 2024-01-05 22:44:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2e5+5;
ll f(ll x){
x--;
ll ans=0;
for(ll l=1,r;r<x;l=r+1){
r=x/(x/l);
ans+=(r-l+1)*(x/l);
}
return ans;
}
void solve(){
ll n,ans=0;cin>>n;
for(ll l=1,r;r<n;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*f(n/l);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 13384ms
memory: 3672kb
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 23868ms
memory: 3672kb
input:
3 90076809172 100000000000 99913139559
output:
30192292781431 33790187414013 33758574429172
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 24470ms
memory: 3504kb
input:
3 99997992652 99832769119 99997176887
output:
33789456663124 33729325483151 33789159765448
result:
ok 3 lines
Test #5:
score: 0
Accepted
time: 6189ms
memory: 3516kb
input:
30 500000004 991026973 875910473 804967563 817240034 859023503 871905363 994897763 533952899 999999996 500000003 851714124 618161807 500000002 500000000 642565501 703104463 520948789 513785485 999999997 1000000000 579195816 999999998 965942980 870891922 571793533 723494232 999999999 590539561 500000...
output:
106931694901 226252654431 197658605222 180202748830 183212809398 193491469207 196669619643 227219558906 114922441260 228494567273 106931693908 191690034392 134938724588 106931693896 106931693226 140788123843 155385451308 111856217326 110170204124 228494567397 228494568703 125643111389 228494567464 2...
result:
ok 30 lines
Test #6:
score: 0
Accepted
time: 2289ms
memory: 3524kb
input:
3000 684920 881740 317776 310160 23336 999832 819596 973868 166 449876 290325 912538 999939 282224 600310 448121 816943 972518 895590 612220 349205 52931 999880 267637 549817 513310 182 852220 314635 377356 96591 628319 999757 597508 896048 116 71393 735158 203 282 68 33305 762621 745035 922434 5853...
output:
67611341 90223986 28005207 27233331 1319648 104127915 83003612 101051578 2569 41769873 25235715 93827427 104140754 24424464 58142642 41582414 82697155 100892535 91843138 59465231 31217321 3478468 104133259 22974376 52576328 48594603 2923 86785163 27686009 34130245 7039269 61257408 104119319 57832117...
result:
ok 3000 lines