QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76845 | #5503. Euclidean Algorithm | gyh20 | ML | 8503ms | 8032kb | C++14 | 1.1kb | 2023-02-12 13:25:51 | 2023-02-12 13:25:53 |
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)
ll Q[450002];
int sum[500002];
ll calc(ll n) {
if(n<=500000)return sum[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,nn=500000; cin>>T;
// T=1;
for(int i=1;i<=nn;++i)
for(int j=i;j<=nn;j+=i)
++sum[j];
for(int i=1;i<=nn;++i)sum[i]+=sum[i-1];
while(T--) {
ll n;
cin>>n;
//n=1e11;
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: 7ms
memory: 5296kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 8503ms
memory: 8032kb
input:
3 29107867360 65171672278 41641960535
output:
8921593237533 21300450379732 13136180138425
result:
ok 3 lines
Test #3:
score: -100
Memory Limit Exceeded
input:
3 90076809172 100000000000 99913139559