QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#850688 | #9962. Diminishing Fractions | Zawos | TL | 1756ms | 216888kb | C++23 | 2.5kb | 2025-01-10 11:11:07 | 2025-01-10 11:11:07 |
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];
ll inv[5217][5217];
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;
for(int i = 0; i < 5217;i++){
for(int j = 0; j < 5217;j++){
if(pot[i].first == pot[j].first) continue;
euclid(pot[j].second,pot[i].second,inv[i][j],y);
if(inv[i][j] <0) inv[i][j] += pot[i].second;
}
}
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*inv[u.second][e.second];
if(a > 1e13) a%= pot[u.second].second;
}
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: 1281ms
memory: 216684kb
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: 1293ms
memory: 216488kb
input:
1 1
output:
1/1
result:
ok OK, t = 1
Test #3:
score: 0
Accepted
time: 1283ms
memory: 216792kb
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: 1288ms
memory: 216756kb
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: 1301ms
memory: 216756kb
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: 1344ms
memory: 216752kb
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: 1506ms
memory: 216888kb
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: 1756ms
memory: 216756kb
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: -100
Time Limit Exceeded
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+...