QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#433362 | #2395. Common Factors | JustJie | WA | 1ms | 4620kb | C++20 | 1.7kb | 2024-06-08 10:37:52 | 2024-06-08 10:37:53 |
Judging History
answer
/***************************************************************************************************
* author : Jie Chen (4th Year CS)
* school : Rochester Institute of Technology
* created: 06.07.2024 22:14:08
****************************************************************************************************/
#include "bits/stdc++.h"
using namespace std;
#ifdef BROKEN_CODE
#include <bits/debug.h>
#else
#define dbg(...) 10082002
#define dbp(...) "Need Internship"
#endif
using i64 = long long;
constexpr int LIM = 2e5 + 10;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n;
cin >> n;
int phi[LIM] {};
i64 cur = 1;
int cnt = 0;
vector<int> prime;
for (int i = 2; i < LIM; i++) {
if (phi[i] == 0) {
phi[i] = i;
if (cur > n / i) {
break;
}
cnt++;
cur = cur * i;
prime.push_back(i);
for (i64 j = i64(i) * i; j < LIM; j += i) {
if (phi[j] != 0) {
break;
}
phi[j] = i;
}
}
}
// 2 3
// 2 3 4 6
// 4 / 6 = 2 / 3
i64 ans = 0;
for (int mask = 1; mask < (1 << cnt); mask++) {
i64 l = 1;
for (int i = 0; i < cnt; i++) {
if (mask & (1 << i)) {
l *= prime[i];
}
}
i64 res = cur / l;
if (__builtin_popcount(mask) & 1) {
ans += res;
} else {
ans -= res;
}
}
i64 g = gcd(ans, cur);
ans /= g;
cur /= g;
cout << ans << "/" << cur << "\n";
}
// ~ Just Jie
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4592kb
input:
2
output:
1/2
result:
ok single line: '1/2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4328kb
input:
5
output:
1/2
result:
ok single line: '1/2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
6
output:
2/3
result:
ok single line: '2/3'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4596kb
input:
29
output:
2/3
result:
ok single line: '2/3'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4360kb
input:
30
output:
11/15
result:
ok single line: '11/15'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
31
output:
11/15
result:
ok single line: '11/15'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4292kb
input:
209
output:
11/15
result:
ok single line: '11/15'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4392kb
input:
210
output:
27/35
result:
ok single line: '27/35'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4560kb
input:
2309
output:
27/35
result:
ok single line: '27/35'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4620kb
input:
2310
output:
61/77
result:
ok single line: '61/77'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4540kb
input:
30000
output:
61/77
result:
ok single line: '61/77'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4568kb
input:
30030
output:
809/1001
result:
ok single line: '809/1001'
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 4300kb
input:
510510
output:
587/715
result:
wrong answer 1st lines differ - expected: '13945/17017', found: '587/715'