QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#77059#5503. Euclidean AlgorithmGolovanov399TL 2ms3304kbC++20631b2023-02-13 00:57:342023-02-13 00:57:35

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-13 00:57:35]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3304kb
  • [2023-02-13 00:57:34]
  • 提交

answer

#include <iostream>

using namespace std;

int nxt() {
	int x;
	cin >> x;
	return x;
}

long long f(long long n) {
	n -= 1;
	long long ans = 0;
	for (long long d = 1; d <= n; d = n / (n / d) + 1) {
		long long k = n / d;
		ans += (n / k - d + 1) * k;
	}
	return ans;
}

void solve() {
	long long n;
	cin >> n;
	long long ans = 0;
	for (long long d = 1; d <= n; d = n / (n / d) + 1) {
		long long k = n / d;
		ans += (n / k - d + 1) * f(k);
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = nxt();
	while (t--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3304kb

input:

3
2
5
14

output:

1
9
62

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

3
29107867360
65171672278
41641960535

output:


result: