QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#586126#2395. Common FactorsTenshiWA 0ms3828kbC++20585b2024-09-24 05:33:592024-09-24 05:33:59

Judging History

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

  • [2024-09-24 05:33:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-09-24 05:33:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define int long long

signed main(){
	int n; cin>>n;
	vector<int> b={2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47};
	int phi=1, cur=1;
	for(auto e: b){
		if(cur*e<=n){
			cur*=e;
		}
		else break;
		phi*=(e-1);
	}
	
	int x=cur-phi, y=cur;
	int g=__gcd(x, y);
	cout<<x/g<<"/"<<y/g<<endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

1/2

result:

ok single line: '1/2'

Test #2:

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

input:

5

output:

1/2

result:

ok single line: '1/2'

Test #3:

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

input:

6

output:

2/3

result:

ok single line: '2/3'

Test #4:

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

input:

29

output:

2/3

result:

ok single line: '2/3'

Test #5:

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

input:

30

output:

11/15

result:

ok single line: '11/15'

Test #6:

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

input:

31

output:

11/15

result:

ok single line: '11/15'

Test #7:

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

input:

209

output:

11/15

result:

ok single line: '11/15'

Test #8:

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

input:

210

output:

27/35

result:

ok single line: '27/35'

Test #9:

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

input:

2309

output:

27/35

result:

ok single line: '27/35'

Test #10:

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

input:

2310

output:

61/77

result:

ok single line: '61/77'

Test #11:

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

input:

30000

output:

61/77

result:

ok single line: '61/77'

Test #12:

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

input:

30030

output:

809/1001

result:

ok single line: '809/1001'

Test #13:

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

input:

510510

output:

13945/17017

result:

ok single line: '13945/17017'

Test #14:

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

input:

510511

output:

13945/17017

result:

ok single line: '13945/17017'

Test #15:

score: -100
Wrong Answer
time: 0ms
memory: 3592kb

input:

9699690

output:

13945/17017

result:

wrong answer 1st lines differ - expected: '268027/323323', found: '13945/17017'