QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#843751#9962. Diminishing Fractionsucup-team1198#WA 144ms3820kbC++143.4kb2025-01-05 00:44:052025-01-05 00:44:05

Judging History

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

  • [2025-01-05 00:44:05]
  • 评测
  • 测评结果:WA
  • 用时:144ms
  • 内存:3820kb
  • [2025-01-05 00:44:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int mul(int a, int b, int MOD) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n, int MOD) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x, MOD);
            n /= 2;
        } else {
            res = mul(res, x, MOD);
            --n;
        }
    }
    return res;
}

const int MAXT = 1e3 + 100;
int val[MAXT];
vector<array<int, 2>> ans[MAXT];

const int MAXN = 5e4;

array<int, 2> get_form(int n) {
    if (n == 1) return {-1, -1};
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            int alpha = 0;
            while (n % p == 0) {
                n /= p;
                ++alpha;
            }
            if (n == 1) return {p, alpha};
            return {-1, -1};
        }
    }
    return {n, 1};
}

array<int, 2> mgcd(int a, int b) {
    if (b == 0) return {1, 0};
    auto res = mgcd(b, a % b);
    int q = a / b;
    return {res[1], res[0] - q * res[1]};
}

int inv(int a, int mod) {
    auto res = mgcd(a, mod);
    return (res[0] % mod + mod) % mod;
}

void solve_() {
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> val[i];
    }
    vector<int> ord(q);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [](int i, int j) { return val[i] < val[j]; });

    vector<array<int, 2>> arr; /// {p^alpha, current 1/x}
    int ptr = 0;
    for (int n = 1; n <= MAXN && ptr < q; ++n) {
        auto res = get_form(n);
        int p = res[0], alpha = res[1];
        if (p != -1) {
            /// cerr << p << " " << alpha << endl;
            int id = -1;
            for (int i = 0; i < (int)arr.size(); ++i) {
                if (arr[i][0] == n / p) {
                    id = i;
                    continue;
                }
                arr[i][1] = mul(arr[i][1], p, arr[i][0]);
            }
            if (id == -1) {
                id = arr.size();
                arr.push_back({n, 1});
            }
            arr[id][0] = n;
            arr[id][1] = 1;
            for (int i = 0; i < (int)arr.size(); ++i) {
                if (i == id) continue;
                arr[id][1] = mul(arr[id][1], arr[i][0], arr[id][0]);
            }
        }
        if (n == val[ord[ptr]]) {
            double sum = 0;
            double mlt = 1;
            for (auto elem : arr) {
                int a = elem[1], b = elem[0];
                int x = inv(a, b);
                sum += (double)x / b;
                mlt /= b;
                ans[ord[ptr]].push_back({x, b});
            }
            int res = round(mlt - sum);
            ans[ord[ptr]].push_back({res, 1});
            ++ptr;
        }
    }
    for (int i = 0; i < q; ++i) {
        bool started = false;
        /// double check = 0;
        for (int j = 0; j < (int)ans[i].size(); ++j) {
            int A = ans[i][j][0], B = ans[i][j][1];
            if (A == 0) continue;
            if (A > 0 && started) {
                cout << "+";
            }
            cout << A << "/" << B;
            /// check += 1.0 * A / B;
            started = true;
        }
        cout << "\n";
        /// cerr << check << endl;
    }
}

/// #define MULTITEST

signed main() {
#ifdef LOCAL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#endif

    int tst = 1;
#ifdef MULTITEST
    cin >> tst;
#endif // MULTITEST
    while (tst--) {
        solve_();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3
6

output:

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

result:

ok OK, t = 2

Test #2:

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

input:

1
1

output:

1/1

result:

ok OK, t = 1

Test #3:

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

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1/1
1/2
1/2+2/3-1/1
3/4+1/3-1/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-2/1
1/8+1/3+2/5+1/7-1/1
3/8+1/9+4/5+5/7-2/1
3/8+1/9+4/5+5/7-2/1

result:

ok OK, t = 10

Test #4:

score: -100
Wrong Answer
time: 144ms
memory: 3732kb

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:



1/2
















































1/2+2/3-1/1



result:

wrong answer Not enough lines of fractions for the 3th test case