QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#863758 | #9962. Diminishing Fractions | hos_lyric | RE | 0ms | 3968kb | C++14 | 3.6kb | 2025-01-19 22:02:18 | 2025-01-19 22:02:20 |
Judging History
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...