QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#433390#2395. Common FactorsJustJie#AC ✓2ms4640kbC++201.7kb2024-06-08 10:48:132024-06-08 10:48:14

Judging History

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

  • [2024-06-08 10:48:14]
  • 评测
  • 测评结果：AC
  • 用时：2ms
  • 内存：4640kb
查看
  • [2024-06-08 10:48:13]
  • 提交

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> primes;
    for (int i = 2; i < LIM; i++) {
        if (phi[i] == 0) {
            phi[i] = i;
            if (cur > n / i) {
                break;
            }
            cnt++;
            cur = cur * i;
            primes.push_back(i);
        }

        for (auto p : primes) {
            if (i * p >= LIM) {
                break;
            }
            phi[i * p] = p;
            if (phi[i] == p) {
                break;
            }
        }
    }

    // 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 *= primes[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
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4400kb

input:

2

output:

1/2

result:

ok single line: '1/2'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4640kb

input:

5

output:

1/2

result:

ok single line: '1/2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

6

output:

2/3

result:

ok single line: '2/3'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4396kb

input:

29

output:

2/3

result:

ok single line: '2/3'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4404kb

input:

30

output:

11/15

result:

ok single line: '11/15'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4408kb

input:

31

output:

11/15

result:

ok single line: '11/15'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4404kb

input:

209

output:

11/15

result:

ok single line: '11/15'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

210

output:

27/35

result:

ok single line: '27/35'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

2309

output:

27/35

result:

ok single line: '27/35'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4628kb

input:

2310

output:

61/77

result:

ok single line: '61/77'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4408kb

input:

30000

output:

61/77

result:

ok single line: '61/77'

Test #12:

score: 0
Accepted
time: 0ms
memory: 4344kb

input:

30030

output:

809/1001

result:

ok single line: '809/1001'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4380kb

input:

510510

output:

13945/17017

result:

ok single line: '13945/17017'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

510511

output:

13945/17017

result:

ok single line: '13945/17017'

Test #15:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

9699690

output:

268027/323323

result:

ok single line: '268027/323323'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4404kb

input:

223092869

output:

268027/323323

result:

ok single line: '268027/323323'

Test #17:

score: 0
Accepted
time: 0ms
memory: 4340kb

input:

223092870

output:

565447/676039

result:

ok single line: '565447/676039'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4636kb

input:

6469693229

output:

565447/676039

result:

ok single line: '565447/676039'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4568kb

input:

6469693230

output:

2358365/2800733

result:

ok single line: '2358365/2800733'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4404kb

input:

200560490130

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #21:

score: 0
Accepted
time: 0ms
memory: 4568kb

input:

1005604901300

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #22:

score: 0
Accepted
time: 1ms
memory: 4320kb

input:

7420738134810

output:

2734683311/3212440751

result:

ok single line: '2734683311/3212440751'

Test #23:

score: 0
Accepted
time: 1ms
memory: 4600kb

input:

304250263527210

output:

112599773191/131710070791

result:

ok single line: '112599773191/131710070791'

Test #24:

score: 0
Accepted
time: 1ms
memory: 4376kb

input:

13082761331670030

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #25:

score: 0
Accepted
time: 2ms
memory: 4600kb

input:

614889782588491410

output:

9968041656757/11573306655157

result:

ok single line: '9968041656757/11573306655157'

Test #26:

score: 0
Accepted
time: 2ms
memory: 4384kb

input:

1000000000000000000

output:

9968041656757/11573306655157

result:

ok single line: '9968041656757/11573306655157'

Test #27:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

500000000000000000

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #28:

score: 0
Accepted
time: 1ms
memory: 4376kb

input:

304250263527209

output:

2734683311/3212440751

result:

ok single line: '2734683311/3212440751'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4384kb

input:

30029

output:

61/77

result:

ok single line: '61/77'

Test #30:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

510509

output:

809/1001

result:

ok single line: '809/1001'

Test #31:

score: 0
Accepted
time: 1ms
memory: 4632kb

input:

9699689

output:

13945/17017

result:

ok single line: '13945/17017'

Test #32:

score: 0
Accepted
time: 0ms
memory: 4328kb

input:

200560490129

output:

2358365/2800733

result:

ok single line: '2358365/2800733'

Test #33:

score: 0
Accepted
time: 0ms
memory: 4348kb

input:

7420738134809

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #34:

score: 0
Accepted
time: 1ms
memory: 4628kb

input:

614889782588491409

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #35:

score: 0
Accepted
time: 0ms
memory: 4640kb

input:

13082761331670029

output:

112599773191/131710070791

result:

ok single line: '112599773191/131710070791'
English 繁體中文 简体中文

服务器时间: 2024-11-29 17:33:53 | 开源项目