QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#843424 | #9962. Diminishing Fractions | ucup-team6275# | WA | 910ms | 4692kb | C++20 | 3.4kb | 2025-01-04 19:05:31 | 2025-01-04 19:05:33 |
Judging History
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