QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#843424#9962. Diminishing Fractionsucup-team6275#WA 910ms4692kbC++203.4kb2025-01-04 19:05:312025-01-04 19:05:33

Judging History

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

  • [2025-01-04 19:05:33]
  • 评测
  • 测评结果:WA
  • 用时:910ms
  • 内存:4692kb
  • [2025-01-04 19:05:31]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <algorithm>

using namespace std;
#define int long long

int extgcd(int a, int b, int &x, int &y) {  // define int ll
    if (a == 0) {
        x = 0, y = 1;
        return b;
    }
    int x1, y1;
    int g = extgcd(b % a, a, x1, y1);
    x = y1 - x1 * (b / a);
    y = x1;
    return g;
}

const int MAXN = 50000 + 10;

void print_one(string& s, int x, int y) {
    if (x < 0) {
        s.push_back('-');
        x = -x;
    } else {
        if (!s.empty()) s.push_back('+');
    }
    s += to_string(x);
    s.push_back('/');
    s += to_string(y);
}

string get_ans(const vector <pair<int, int>>& me, int cur_c) {
    string flex;
    bool is_f = true;
    for (auto i : me) {
        print_one(flex, i.first, i.second);
    }

    if (cur_c > 0) {
        while (cur_c--) {
            print_one(flex, 1, 1);
        }
    } else {
        cur_c = -cur_c;
        while (cur_c--) {
            print_one(flex, -1, 1);
        }
    }
    return flex;
}

int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    vector <int> queries(t);
    vector <vector <int>> flex(MAXN);
    for (int i = 0; i < t; ++i) {
        cin >> queries[i];
        flex[queries[i]].push_back(i);
    }
    vector <string> answer(t);

    int cur_c = 1;
    vector <pair <int, int>> now;

    for (int n = 1; n < MAXN; ++n) {
        if (n == 1) {
            for (auto i : flex[n]) {
                answer[i] = get_ans(now, cur_c);
            }
            continue;
        }

        int p = -1;
        for (int j = 2; j * j <= n; ++j) {
            if (n % j == 0) {
                p = j;
                break;
            }
        }

        int k = 0;
        int nn = n;
        if (p == -1) {
            p = n;
        }

        while (nn % p == 0) {
            nn /= p;
            k++;
        }

        if (nn != 1) {
            for (auto i : flex[n]) {
                answer[i] = get_ans(now, cur_c);
//                cout << now.size() << " " << cur_c << endl;
            }
            continue;
        }

        vector <pair <int, int>> nnow;

        auto add = [&](int num1, int b) {
                if (num1 > 0) {
                    cur_c += num1 / b;
                    num1 %= b;
                } else if (num1 < 0) {
                    int bob = (num1 % b + b) % b;
                    cur_c -= (bob - num1) / b;
                    num1 = bob;
                }

                if (num1 != 0) {
                    nnow.emplace_back(num1, b);
                }
        };

        int coef_p = cur_c;
        cur_c = 0;
        for (auto par : now) {
            int a = par.first;
            int b = par.second;

            if (b % p == 0) {
                nnow.emplace_back(a, b * p);
                continue;
            }

            int i, j;
            extgcd(p, b, i, j);

            int num1 = a * i;
            add(num1, b);

            coef_p += j * a;
        }

        add(coef_p, p);
        now.swap(nnow);

        for (auto i : flex[n]) {
            answer[i] = get_ans(now, cur_c);
        }
    }
    for (auto i : answer) cout << i << "\n";
    return 0;
}

/*

 */

详细

Test #1:

score: 100
Accepted
time: 906ms
memory: 4612kb

input:

2
3
6

output:

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

result:

ok OK, t = 2

Test #2:

score: 0
Accepted
time: 906ms
memory: 4692kb

input:

1
1

output:

1/1

result:

ok OK, t = 1

Test #3:

score: -100
Wrong Answer
time: 910ms
memory: 4684kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

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

result:

wrong answer Too many fractions on this line; n = 5