QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#586127 | #2395. Common Factors | Tenshi | AC ✓ | 0ms | 3824kb | C++20 | 600b | 2024-09-24 05:37:28 | 2024-09-24 05:37:28 |
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, 19, 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);
}
debug(cur);
int x=cur-phi, y=cur;
int g=__gcd(x, y);
cout<<x/g<<"/"<<y/g<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
2
output:
1/2
result:
ok single line: '1/2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5
output:
1/2
result:
ok single line: '1/2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6
output:
2/3
result:
ok single line: '2/3'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
29
output:
2/3
result:
ok single line: '2/3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
30
output:
11/15
result:
ok single line: '11/15'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
31
output:
11/15
result:
ok single line: '11/15'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
209
output:
11/15
result:
ok single line: '11/15'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
210
output:
27/35
result:
ok single line: '27/35'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
2309
output:
27/35
result:
ok single line: '27/35'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2310
output:
61/77
result:
ok single line: '61/77'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
30000
output:
61/77
result:
ok single line: '61/77'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
30030
output:
809/1001
result:
ok single line: '809/1001'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
510510
output:
13945/17017
result:
ok single line: '13945/17017'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
510511
output:
13945/17017
result:
ok single line: '13945/17017'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
9699690
output:
268027/323323
result:
ok single line: '268027/323323'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
223092869
output:
268027/323323
result:
ok single line: '268027/323323'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
223092870
output:
565447/676039
result:
ok single line: '565447/676039'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
6469693229
output:
565447/676039
result:
ok single line: '565447/676039'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
6469693230
output:
2358365/2800733
result:
ok single line: '2358365/2800733'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
200560490130
output:
73551683/86822723
result:
ok single line: '73551683/86822723'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
1005604901300
output:
73551683/86822723
result:
ok single line: '73551683/86822723'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
7420738134810
output:
2734683311/3212440751
result:
ok single line: '2734683311/3212440751'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
304250263527210
output:
112599773191/131710070791
result:
ok single line: '112599773191/131710070791'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
13082761331670030
output:
4860900544813/5663533044013
result:
ok single line: '4860900544813/5663533044013'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
614889782588491410
output:
9968041656757/11573306655157
result:
ok single line: '9968041656757/11573306655157'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1000000000000000000
output:
9968041656757/11573306655157
result:
ok single line: '9968041656757/11573306655157'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
500000000000000000
output:
4860900544813/5663533044013
result:
ok single line: '4860900544813/5663533044013'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
304250263527209
output:
2734683311/3212440751
result:
ok single line: '2734683311/3212440751'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
30029
output:
61/77
result:
ok single line: '61/77'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
510509
output:
809/1001
result:
ok single line: '809/1001'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
9699689
output:
13945/17017
result:
ok single line: '13945/17017'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
200560490129
output:
2358365/2800733
result:
ok single line: '2358365/2800733'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
7420738134809
output:
73551683/86822723
result:
ok single line: '73551683/86822723'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
614889782588491409
output:
4860900544813/5663533044013
result:
ok single line: '4860900544813/5663533044013'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
13082761331670029
output:
112599773191/131710070791
result:
ok single line: '112599773191/131710070791'