QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863758#9962. Diminishing Fractionshos_lyricRE 0ms3968kbC++143.6kb2025-01-19 22:02:182025-01-19 22:02:20

Judging History

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

  • [2025-01-19 22:02:20]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3968kb
  • [2025-01-19 22:02:18]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// a x + b y = (+/-) gcd(a, b)
//   (a, 0): g = a, x = 1, y = 0
//   (0, b), (b, b), (-b, b) (b != 0): g = b, x = 0, y = 1
//   otherwise: 2 |x| <= |b|, 2 |y| <= |a|
// S: signed integer
template <class S> S gojo(S a, S b, S &x, S &y) {
  if (b != 0) {
    const S g = gojo(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
  } else {
    x = 1;
    y = 0;
    return a;
  }
}


/*
  \sum[i] x[i]/p[i]^e[i] \in \Z
  <=> ((\prod[j] p[j]^e[j]) / p[i]^e[i]) x[i] == 1  (mod p[i]^e[i])
*/

constexpr int N = 100;
int lpf[N];
int psLen;
int ps[N], qs[N];
Int ms[N], prods[N];

bool asked[N];
string ans[N];

int main() {
  int T;
  for (; ~scanf("%d", &T); ) {
    vector<int> Ns(T);
    for (int t = 0; t < T; ++t) {
      scanf("%d", &Ns[t]);
    }
    
    fill(asked, asked + N, false);
    for (int t = 0; t < T; ++t) asked[Ns[t]] = true;
    
    for (int p = 2; p < N; ++p) lpf[p] = p;
    psLen = 0;
    for (int p = 2; p < N; ++p) if (lpf[p] == p) {
      ps[psLen++] = p;
      for (int n = p; n < N; n += p) chmin(lpf[n], p);
    }
    for (int i = 0; i < psLen; ++i) {
      const int p = ps[i];
      int &q = qs[i];
      for (q = p; q <= N / p; q *= p) {}
      ms[i] = 1;
      prods[i] = 1;
    }
// cerr<<"qs = ";pv(qs,qs+psLen);
    for (int n = 2; n < N; ++n) {
      {
        const int p = lpf[n];
        int nn = n;
        do { nn /= p; } while (nn % p == 0);
        if (nn == 1) {
          for (int i = 0; i < psLen; ++i) {
            if (ps[i] == p) {
              ms[i] *= p;
            } else {
              (prods[i] *= p) %= qs[i];
            }
          }
        }
      }
      if (asked[n]) {
// cerr<<"n = "<<n<<endl;
        double sum = 0.0;
        for (int i = 0; i < psLen && ps[i] <= n; ++i) {
// cerr<<"  "<<prods[i]<<"^-1 mod "<<ms[i]<<endl;
          Int x, y;
          gojo(prods[i], ms[i], x, y);
          if ((x %= ms[i]) < 0) x += ms[i];
          sum += (double)x / ms[i];
          ans[n] += '+';
          ans[n] += to_string(x);
          ans[n] += '/';
          ans[n] += to_string(ms[i]);
        }
        const int x0 = -round(sum - 0.25);
        if (x0) ans[n] = to_string(x0) + "/1" + ans[n];
        if (ans[n][0] == '+') ans[n] = ans[n].substr(1);
      }
    }
    ans[1] = "1/1";
    
    for (int t = 0; t < T; ++t) {
      puts(ans[Ns[t]].c_str());
    }
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3968kb

input:

2
3
6

output:

-1/1+1/2+2/3
-2/1+3/4+2/3+3/5

result:

ok OK, t = 2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

1
1

output:

1/1

result:

ok OK, t = 1

Test #3:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1/1
1/2
-1/1+1/2+2/3
-1/1+3/4+1/3
-2/1+3/4+2/3+3/5
-2/1+3/4+2/3+3/5
-2/1+1/4+2/3+4/5+2/7
-1/1+1/8+1/3+2/5+1/7
-2/1+3/8+1/9+4/5+5/7
-2/1+3/8+1/9+4/5+5/7

result:

ok OK, t = 10

Test #4:

score: 0
Accepted
time: 0ms
memory: 3840kb

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/1+1/4+2/3+4/5+2/7
-5/1+15/16+5/9+3/5+2/7+9/11+4/13+12/17+15/19
1/2
-1/1+1/2+2/3
-1/1+3/4+1/3
-2/1+3/4+2/3+3/5
-2/1+3/4+2/3+3/5
-2/1+1/4+2/3+4/5+2/7
-1/1+1/8+1/3+2/5+1/7
-2/1+3/8+1/9+4/5+5/7
-2/1+3/8+1/9+4/5+5/7
-2/1+1/8+5/9+4/5+3/7+1/11
-2/1+1/8+5/9+4/5+3/7+1/11
-4/1+5/8+8/9+3/5+4/7+6/11+10/13
-4...

result:

ok OK, t = 54

Test #5:

score: -100
Runtime Error

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:


result: