QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850733 | #9962. Diminishing Fractions | Zawos | TL | 1137ms | 4324kb | C++23 | 2.4kb | 2025-01-10 11:29:01 | 2025-01-10 11:29:23 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int N = 50001;
int wh[N];
int euclid(int a, int b, ll &x, ll &y) {
if (!b) return x = 1, y = 0, a;
int d = euclid(b, a % b, y, x);
return y -= a/b * x, d;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(wh,-1,sizeof(wh));
vector<int> prime(N+1,1);
for(int i = 2; i <= N; i++){
if(prime[i] == 1) for(int j = i; j <=N;j+=i) prime[j] = i;
}
vector<pair<int,int>> pot;
for(int i = 2; i <= N;i++){
unordered_map<int,int> fac;
int x = i;
int r = 1;
while( x > 1){
fac[prime[x]]++;
r *= prime[x];
x /= prime[x];
if(fac.size() > 1) break;
}
if(fac.size() == 1){
for(auto &u: fac) pot.push_back({u.first,r});
}
}
for(int i = 0; i < 5217;i++) wh[pot[i].second] = i;
ll y;
int t;
cin >>t;
while(t--){
int n;
cin >> n;
if(n == 1){
cout <<"1/1\n";
continue;
}else if(n == 2){
cout <<"1/2\n";
continue;
}
unordered_map<int,int> mp;
for(int i = 1; i <= n; i++){
if(wh[i] != -1){
mp[pot[wh[i]].first] = wh[i];
}
}
double ans = 0.0;
int co = 0;
for(auto &u: mp){
ll a = 1;
for(auto &e:mp){
if(u.first == e.first) continue;
a =a*pot[e.second].second;
if(a > 1e13) a%= pot[u.second].second;
}
a%= pot[u.second].second;
euclid(a,pot[u.second].second,a,y);
if(a <0) a += pot[u.second].second;
if(co > 0)cout<<'+';
cout<<a<<"/"<<pot[u.second].second;
co++;
ans += (double)a/(double)pot[u.second].second;
}
ans += 0.5;
cout<<"-"<<floor(ans)<<"/1\n";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 4112kb
input:
2 3 6
output:
2/3+1/2-1/1 3/5+2/3+3/4-2/1
result:
ok OK, t = 2
Test #2:
score: 0
Accepted
time: 4ms
memory: 3836kb
input:
1 1
output:
1/1
result:
ok OK, t = 1
Test #3:
score: 0
Accepted
time: 2ms
memory: 4024kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1/1 1/2 2/3+1/2-1/1 1/3+3/4-1/1 3/5+2/3+3/4-2/1 3/5+2/3+3/4-2/1 2/7+4/5+2/3+1/4-2/1 1/7+2/5+1/3+1/8-1/1 5/7+4/5+1/9+3/8-2/1 5/7+4/5+1/9+3/8-2/1
result:
ok OK, t = 10
Test #4:
score: 0
Accepted
time: 4ms
memory: 4176kb
input:
54 7 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 3 47 81
output:
2/7+4/5+2/3+1/4-2/1 15/19+12/17+4/13+9/11+2/7+3/5+5/9+15/16-5/1 1/2 2/3+1/2-1/1 1/3+3/4-1/1 3/5+2/3+3/4-2/1 3/5+2/3+3/4-2/1 2/7+4/5+2/3+1/4-2/1 1/7+2/5+1/3+1/8-1/1 5/7+4/5+1/9+3/8-2/1 5/7+4/5+1/9+3/8-2/1 1/11+3/7+4/5+5/9+1/8-2/1 1/11+3/7+4/5+5/9+1/8-2/1 10/13+6/11+4/7+3/5+8/9+5/8-4/1 10/13+6/11+4/7+...
result:
ok OK, t = 54
Test #5:
score: 0
Accepted
time: 5ms
memory: 4076kb
input:
92 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 255 258 261 264 267 270 273 276 279 282 28...
output:
21/47+30/43+26/41+2/27+24/29+21/25+27/32+18/31+26/49+10/11+21/37+2/13+11/17+8/19+19/23-9/1 11/53+27/47+3/43+9/41+25/27+1/29+7/25+15/32+29/31+31/49+6/11+36/37+2/13+14/17+17/19+6/23-8/1 11/53+27/47+3/43+9/41+25/27+1/29+7/25+15/32+29/31+31/49+6/11+36/37+2/13+14/17+17/19+6/23-8/1 45/59+46/53+14/47+19/43...
result:
ok OK, t = 92
Test #6:
score: 0
Accepted
time: 50ms
memory: 4116kb
input:
1000 622 149 839 472 292 345 799 941 449 15 907 494 48 430 505 66 83 97 10 548 286 644 528 249 573 860 557 932 746 262 971 157 603 715 984 333 53 916 784 649 70 768 780 64 118 616 979 466 24 2 517 774 566 419 182 222 40 169 951 830 977 383 355 770 134 973 917 3 854 31 35 825 109 945 671 536 952 888 ...
output:
429/619+398/599+545/593+425/577+260/563+496/557+508/541+448/509+179/503+340/499+156/491+454/479+2/467+148/463+389/461+8/457+372/449+37/443+163/439+159/431+379/419+334/409+149/401+371/397+166/389+278/379+257/373+49/613+29/359+63/607+257/353+282/349+69/601+212/347+141/331+20/571+303/317+209/311+156/54...
result:
ok OK, t = 1000
Test #7:
score: 0
Accepted
time: 216ms
memory: 4176kb
input:
1000 1748 1741 1576 1940 1648 1825 1183 1447 1318 1277 1913 1208 1417 1388 1143 1581 1222 1904 1407 1006 1175 1218 1734 1934 1003 1704 1984 1399 1333 1840 1317 1233 1133 1232 1776 1881 1476 1712 1401 1231 1978 1964 1419 1644 1103 1498 1454 1480 1377 1352 1837 1616 1009 1413 1199 1977 1477 1579 1920 ...
output:
493/1747+226/1733+774/1721+302/1709+1534/1697+952/1693+1511/1667+346/1663+1063/1657+884/1637+739/1627+518/709+190/1223+268/691+298/683+190/677+91/163+237/661+419/653+77/139+788/1723+611/641+92/127+516/631+177/619+354/599+504/593+20/79+450/1621+561/577+220/1091+198/563+408/557+21/43+354/541+309/509+3...
result:
ok OK, t = 1000
Test #8:
score: 0
Accepted
time: 460ms
memory: 4324kb
input:
1000 2107 2115 2985 2832 2564 2529 2971 2637 2666 2172 2496 2191 2465 2199 2260 2161 2402 2369 2762 2674 2734 2252 2488 2185 2652 2014 2018 2960 2313 2063 2696 2976 2457 2247 2180 2647 2907 2901 2912 2538 2512 2623 2267 2986 2348 2170 2131 2166 2563 2111 2860 2254 2462 2080 2054 2803 2397 2778 2411 ...
output:
1387/2099+1830/2089+1367/2087+1852/2083+1980/2081+1368/2069+12/2063+698/2039+554/2027+257/2017+243/2003+577/1999+1183/1997+1770/1987+1942/1979+461/1973+1151/1951+644/1949+924/1933+1419/1931+463/1913+1672/1907+904/1901+1800/1889+1341/1877+903/1873+730/1871+1729/1867+985/1861+1063/1847+1586/1831+245/1...
result:
ok OK, t = 1000
Test #9:
score: 0
Accepted
time: 807ms
memory: 4032kb
input:
1000 3416 3784 3793 3610 3982 3174 3253 3088 3197 3926 3664 3669 3431 3821 3340 3298 3498 3627 3194 3354 3362 3512 3865 3529 3988 3973 3852 3552 3672 3282 3035 3639 3998 3090 3771 3618 3402 3139 3903 3110 3452 3947 3941 3225 3187 3283 3243 3722 3808 3491 3309 3935 3937 3259 3909 3665 3809 3390 3285 ...
output:
2339/3407+1614/3389+2094/3371+2719/3361+1966/3331+996/3323+807/3301+2926/3271+2385/3229+2495/3221+1021/3217+2026/3209+2119/3191+1924/3187+1342/3167+1255/3137+3021/3119+679/3089+2613/3067+2982/3049+931/3037+283/3019+785/3011+2014/3001+349/2999+861/2969+2859/2963+2830/2957+1140/2939+44/2927+2819/2917+...
result:
ok OK, t = 1000
Test #10:
score: 0
Accepted
time: 1137ms
memory: 4080kb
input:
899 4695 4616 4545 4771 4315 4850 4821 4722 4493 4338 4566 4144 4721 4334 4536 4313 4264 4669 4648 4780 4551 4044 4506 4798 4483 4372 4371 4636 4650 4590 4340 4383 4756 4104 4077 4067 4692 4008 4141 4610 4532 4751 4345 4498 4214 4621 4519 4505 4681 4726 4011 4879 4103 4283 4470 4844 4520 4740 4333 4...
output:
746/4679+2864/4673+2479/4657+3859/4651+1069/4649+1633/4643+40/4639+589/4637+4512/4621+51/4597+656/4591+52/4583+1231/4561+3075/4547+2130/4523+391/4517+109/4513+1087/4493+1891/4481+2862/4463+1311/4451+1448/4423+4394/4409+244/4391+1532/4373+1383/4363+3892/4357+2399/4339+744/4337+4211/4327+2012/4297+369...
result:
ok OK, t = 899
Test #11:
score: 0
Accepted
time: 1119ms
memory: 4216kb
input:
1000 3798 4097 3356 3197 4364 3360 3927 4704 4072 3229 3681 3276 4187 4013 4014 3134 3743 3208 4792 3235 4788 3953 3313 4147 3230 3497 3181 4376 4631 3710 3602 4191 3405 3381 4722 3607 4374 3037 3149 3682 3557 3338 4471 3242 4470 4753 4637 3343 3625 4516 3505 3553 3626 3073 3222 4514 4402 4063 3372 ...
output:
1071/3797+612/3779+1357/3727+3339/3719+434/3701+1817/3697+202/3671+2909/3659+3114/3637+3525/3607+1055/3581+1449/3571+930/3547+2482/3533+1025/3511+3023/3449+1838/3407+607/3389+729/3371+2826/3361+2899/3331+1982/3323+2421/3301+2534/3271+2517/3229+1744/3221+2375/3217+124/3209+2185/3191+2987/3187+1210/31...
result:
ok OK, t = 1000
Test #12:
score: -100
Time Limit Exceeded
input:
474 7545 5913 9012 7937 9033 8958 6042 9802 6773 7104 7992 7475 7128 5208 6469 5645 7483 49664 7929 9114 8828 7916 9405 6829 8448 8454 9204 7795 5960 6310 9545 49393 8789 5482 8149 7405 8428 7210 5902 8761 5209 8251 7599 9264 5237 8710 6878 8842 5430 9871 8230 8959 9001 8926 9201 5003 8737 7628 7133...
output:
3477/7529+2131/7523+3048/7489+587/7487+6470/7457+5459/7433+6044/7417+1464/7369+6215/7351+5686/7349+2113/7321+7214/7309+5534/7283+3299/7243+2345/7219+1011/7207+2060/7193+661/7159+3972/7109+3365/7039+48/6997+4923/6983+6671/6959+3398/6949+2389/6907+5941/6899+5977/6871+3757/6863+6409/6841+195/6823+1601/...