QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89922#5503. Euclidean Algorithminstallb#TL 29937ms7624kbC++20786b2023-03-21 19:46:182023-03-21 19:46:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-21 19:46:22]
  • 评测
  • 测评结果:TL
  • 用时:29937ms
  • 内存:7624kb
  • [2023-03-21 19:46:18]
  • 提交

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

output:


result: