QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#77768 | #5503. Euclidean Algorithm | XKError | TL | 23ms | 7464kb | C++ | 730b | 2023-02-15 16:17:56 | 2023-02-15 16:17:58 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
ll n;
int d[maxn];
ll ds(ll x) {
if (x < maxn) return d[x];
ll res = 0;
for (ll l = 1, r; l <= x; l = r + 1) {
r = x / (x / (double)(l));
res += x / (double)(l) * (r - l + 1);
}
return res;
}
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i < maxn; i++) {
for (int j = i; j < maxn; j += i) {
++d[j];
}
d[i] += d[i - 1];
}
while (T--) {
scanf("%lld", &n);
ll res = 0, lst = 0;
for (ll l = 1, r; l <= n; l = r + 1) {
r = n / (n / (double)(l));
ll now = ds(r - 1);
res += (now - lst) * (n / l);
lst = now;
}
printf("%lld\n", res);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 23ms
memory: 7464kb
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