QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77937#5503. Euclidean AlgorithmjeffqiML 0ms0kbC++141.2kb2023-02-15 23:49:382023-02-15 23:49:42

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-15 23:49:42]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-02-15 23:49:38]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define grep(i,u) for (int i = head[u],v = e[i].v; i; v = e[i = e[i].nxt].v)
#define LL long long
#define il inline
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
il LL read() {
	LL x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
	while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
namespace qiqi {
	const int N = 12e5+1; LL n; int d[N];
	il void init(int n) {
		rep(i,1,n) {
			rep(j,1,n/i) ++d[i*j];
			d[i] += d[i-1];
		}
	}
	il LL calc(LL n) {
		if (n < N) return d[n]; LL res = 0;
		for (LL l = 1,r; l <= n; l = r+1) {
			r = n/(n/l); res += n/l*(r-l+1);
		}
		return res;
	}
	void main() {
		LL ans = 0,lst = 0; n = read();
		for (LL l = 1,r; l <= n; l = r+1) {
			r = n/(n/l); LL cur = calc(r-1);
			ans += n/l*(cur-lst); lst = cur;
		}
		printf("%lld\n",ans);
	}
}
int main() {
	qiqi::init(qiqi::N-1); int T = read(); while (T--) qiqi::main(); return 0;
}

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

3
2
5
14

output:

1
9
62

result: