QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850688#9962. Diminishing FractionsZawosTL 1756ms216888kbC++232.5kb2025-01-10 11:11:072025-01-10 11:11:07

Judging History

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

  • [2025-01-10 11:11:07]
  • 评测
  • 测评结果:TL
  • 用时:1756ms
  • 内存:216888kb
  • [2025-01-10 11:11:07]
  • 提交

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+...

result: