QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#586126 | #2395. Common Factors | Tenshi | WA | 0ms | 3828kb | C++20 | 585b | 2024-09-24 05:33:59 | 2024-09-24 05:33:59 |
Judging History
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'