QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#77933 | #5503. Euclidean Algorithm | jeffqi | WA | 108ms | 7488kb | C++14 | 1.2kb | 2023-02-15 23:45:20 | 2023-02-15 23:45:23 |
Judging History
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 = 1e6+1; int n,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: 100
Accepted
time: 28ms
memory: 7480kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 108ms
memory: 7488kb
input:
3 29107867360 65171672278 41641960535
output:
0 166081978924 0
result:
wrong answer 1st lines differ - expected: '8921593237533', found: '0'