QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76842#5503. Euclidean Algorithmgyh20TL 29380ms7972kbC++14962b2023-02-12 13:21:112023-02-12 13:21:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-12 13:21:15]
  • 评测
  • 测评结果:TL
  • 用时:29380ms
  • 内存:7972kb
  • [2023-02-12 13:21:11]
  • 提交

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

result: