QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#76844#5503. Euclidean Algorithmgyh20ML 31ms7344kbC++141.1kb2023-02-12 13:24:192023-02-12 13:24:20

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:24:20]
  • 评测
  • 测评结果:ML
  • 用时:31ms
  • 内存:7344kb
  • [2023-02-12 13:24:19]
  • 提交

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[500002];
int sum[1000002];
ll calc(ll n) {
	if(n<=1000000)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=1000000; 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;
}

详细

Test #1:

score: 100
Accepted
time: 31ms
memory: 7344kb

input:

3
2
5
14

output:

1
9
62

result:

ok 3 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

3
29107867360
65171672278
41641960535

output:


result: