QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19228#2395. Common FactorsQingyuAC ✓4ms3792kbC++20566b2022-01-28 15:18:392022-05-06 04:29:17

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 04:29:17]
  • Judged
  • Verdict: AC
  • Time: 4ms
  • Memory: 3792kb
Show
  • [2022-01-28 15:18:39]
  • Submitted

answer

#include <bits/stdc++.h>

int main() {
	long long n;
	std::cin >> n;
	auto is_prime = [&](long long x) {
		if (x == 1) return false;
		if (x == 2) return true;
		if (x % 2 == 0) return false;
		for (long long i = 2; i * i <= x; ++i)
			if (x % i == 0)
				return false;
		return true;
	};
	long long prod = 1, p = 1, q = 1;
	for (long long i = 2; ; ++i)
		if (is_prime(i)) {
			if (prod > n / i) break;
			prod *= i;
			p *= i - 1, q *= i;
			long long g = std::gcd(p, q);
			p /= g, q /= g;
		}
	p = q - p;
	printf("%lld/%lld", p, q);
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3708kb

input:

2

output:

1/2

result:

ok single line: '1/2'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

5

output:

1/2

result:

ok single line: '1/2'

Test #3:

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

input:

6

output:

2/3

result:

ok single line: '2/3'

Test #4:

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

input:

29

output:

2/3

result:

ok single line: '2/3'

Test #5:

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

input:

30

output:

11/15

result:

ok single line: '11/15'

Test #6:

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

input:

31

output:

11/15

result:

ok single line: '11/15'

Test #7:

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

input:

209

output:

11/15

result:

ok single line: '11/15'

Test #8:

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

input:

210

output:

27/35

result:

ok single line: '27/35'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

2309

output:

27/35

result:

ok single line: '27/35'

Test #10:

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

input:

2310

output:

61/77

result:

ok single line: '61/77'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

30000

output:

61/77

result:

ok single line: '61/77'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

30030

output:

809/1001

result:

ok single line: '809/1001'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

510510

output:

13945/17017

result:

ok single line: '13945/17017'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

510511

output:

13945/17017

result:

ok single line: '13945/17017'

Test #15:

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

input:

9699690

output:

268027/323323

result:

ok single line: '268027/323323'

Test #16:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

223092869

output:

268027/323323

result:

ok single line: '268027/323323'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

223092870

output:

565447/676039

result:

ok single line: '565447/676039'

Test #18:

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

input:

6469693229

output:

565447/676039

result:

ok single line: '565447/676039'

Test #19:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

6469693230

output:

2358365/2800733

result:

ok single line: '2358365/2800733'

Test #20:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

200560490130

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #21:

score: 0
Accepted
time: 3ms
memory: 3668kb

input:

1005604901300

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #22:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

7420738134810

output:

2734683311/3212440751

result:

ok single line: '2734683311/3212440751'

Test #23:

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

input:

304250263527210

output:

112599773191/131710070791

result:

ok single line: '112599773191/131710070791'

Test #24:

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

input:

13082761331670030

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #25:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

614889782588491410

output:

9968041656757/11573306655157

result:

ok single line: '9968041656757/11573306655157'

Test #26:

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

input:

1000000000000000000

output:

9968041656757/11573306655157

result:

ok single line: '9968041656757/11573306655157'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

500000000000000000

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #28:

score: 0
Accepted
time: 3ms
memory: 3640kb

input:

304250263527209

output:

2734683311/3212440751

result:

ok single line: '2734683311/3212440751'

Test #29:

score: 0
Accepted
time: 4ms
memory: 3656kb

input:

30029

output:

61/77

result:

ok single line: '61/77'

Test #30:

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

input:

510509

output:

809/1001

result:

ok single line: '809/1001'

Test #31:

score: 0
Accepted
time: 3ms
memory: 3736kb

input:

9699689

output:

13945/17017

result:

ok single line: '13945/17017'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

200560490129

output:

2358365/2800733

result:

ok single line: '2358365/2800733'

Test #33:

score: 0
Accepted
time: 3ms
memory: 3620kb

input:

7420738134809

output:

73551683/86822723

result:

ok single line: '73551683/86822723'

Test #34:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

614889782588491409

output:

4860900544813/5663533044013

result:

ok single line: '4860900544813/5663533044013'

Test #35:

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

input:

13082761331670029

output:

112599773191/131710070791

result:

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

Server Time: 2025-02-13 02:32:20 | OpenSource Project