QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89922 | #5503. Euclidean Algorithm | installb# | TL | 29937ms | 7624kb | C++20 | 786b | 2023-03-21 19:46:18 | 2023-03-21 19:46:22 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
typedef long long ll;
const int N=1e6;
ll x;int T,f[N+10];
ll sum(ll n){
if(n<=N) return f[n];
ll ans=0;
for(ll l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*(n/l);
}
return ans;
}
ll cal(ll n){
ll ans=0;
for(ll l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*sum(n/l-1);
}
return ans;
}
void pre(int n){
rep(i,1,n) rep(j,1,n/i) f[i*j]++;
rep(i,1,n) f[i]+=f[i-1];
}
int main(){
//cerr << sizeof(f)/1024/1024 << endl;
scanf("%d",&T);pre(N);
while(T--){
scanf("%lld",&x);
printf("%lld\n",cal(x));
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 25ms
memory: 7624kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 14060ms
memory: 7484kb
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 29937ms
memory: 7484kb
input:
3 90076809172 100000000000 99913139559
output:
30192292781431 33790187414013 33758574429172
result:
ok 3 lines
Test #4:
score: -100
Time Limit Exceeded
input:
3 99997992652 99832769119 99997176887