QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433362#2395. Common FactorsJustJieWA 1ms4620kbC++201.7kb2024-06-08 10:37:522024-06-08 10:37:53

Judging History

你现在查看的是最新测评结果

  • [2024-06-08 10:37:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4620kb
  • [2024-06-08 10:37:52]
  • 提交

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'