QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#843751 | #9962. Diminishing Fractions | ucup-team1198# | WA | 144ms | 3820kb | C++14 | 3.4kb | 2025-01-05 00:44:05 | 2025-01-05 00:44:05 |
Judging History
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