QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76842 | #5503. Euclidean Algorithm | gyh20 | TL | 29380ms | 7972kb | C++14 | 962b | 2023-02-12 13:21:11 | 2023-02-12 13:21:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int read();
typedef long long ll;
#define fr(i,l,r) for(int i=(l);i<=(r);++i)
#define rf(i,l,r) for(int i=(l);i>=(r);--i)
#define fo(i,l,r) for(int i=(l);i<(r);++i)
#define foredge(i,u,v) for(int i=fir[u],v;v=to[i],i;i=nxt[i])
#define filein(file) freopen(file".in","r",stdin)
#define fileout(file) freopen(file".out","w",stdout)
double inv[500002];
ll Q[500002];
ll calc(ll n) {
ll ans=0;int k=sqrt(2*n);
for(int i=1;i<=k;++i)ans+=Q[i]=n/i;
for(ll l=k+1,r,tmp;l<=n;l=r+1) {
r=Q[tmp=n/l];
ans+=tmp*(r-l+1);
}
return ans;
}
int main() {
int T; cin>>T;
while(T--) {
ll n;
cin>>n;
ll ans=0;
for(ll l=1,r;l<=n;l=r+1) {
r=n/(n/l);
ans+=calc(n/l-1)*(r-l+1);
}
cout<<ans<<endl;
}
return 0;
}
int read() {
static int x,c,f; x=0,f=1;
do c=getchar(),(c=='-'&&(f=-1)); while(!isdigit(c));
do x=x*10+(c&15),c=getchar(); while(isdigit(c));
return x*f;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3312kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 16639ms
memory: 7028kb
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 29380ms
memory: 7972kb
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:
33789456663124 33729325483151