QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584348 | #9381. 502 Bad Gateway | Jiyeon | Compile Error | / | / | C++14 | 3.0kb | 2024-09-23 12:57:23 | 2024-09-23 12:57:24 |
Judging History
你现在查看的是最新测评结果
- [2024-09-24 14:55:37]
- hack成功,自动添加数据
- (/hack/886)
- [2024-09-23 12:57:24]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2024-09-23 12:57:23]
- 提交
answer
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
struct fac {
int x, y;
fac(int numerator = 0, int denominator = 1) {
x = numerator;
y = denominator;
simplify();
}
void simplify() {
int g = gcd(x, y);
x /= g;
y /= g;
if (y < 0) {
x = -x;
y = -y;
}
}
bool operator<(const fac& other) const {
return x * other.y < other.x * y;
}
fac operator+(const fac& other) const {
int newX = x * other.y + other.x * y;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator-(const fac& other) const {
int newX = x * other.y - other.x * y;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator*(const fac& other) const {
int newX = x * other.x;
int newY = y * other.y;
return fac(newX, newY);
}
fac operator/(const fac& other) const {
int newX = x * other.y;
int newY = y * other.x;
return fac(newX, newY);
}
void print() const {
cout << (long long)x << "/" << (long long)y << std::endl;
}
};
int n;
fac calc(int end)
{
fac old = fac(n+1, 2);
fac first = old - (fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n));
// (fac(end * (end + 1) / 2, n)).print();
// fac((n - end) * (n * (n + 1) / 2 + n), n * n).print();
// cout << n * (n + 1) / 2 + n << endl;
// ((fac(end * (end + 1) / 2, n) + fac((n - end) * (n * (n + 1) / 2 + n), n * n))).print();
// first.print();
fac q = fac(n - end , n);
// q.print();
fac ans = fac(n + 1, 2) - first / (fac(1, 1) - q);
// cout << ans.x << " " << ans.y << " " << ans.x * 1.0 / ans.y << endl;
return ans;
}
void solve()
{
long long nn;
cin >> nn;
n = nn;
// cin >> n;
// int end = (n+2)/2;
int l = 1, r = n;
while(r - l > 2) {
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
fac f1 = calc(midl);
fac f2 = calc(midr);
if (f1 < f2) { // 如果 f(m1) < f(m2),说明最小值在 [l, m2] 区间
r = midr - 1;
} else { // 如果 f(m1) >= f(m2),说明最小值在 [m1, r] 区间
l = midl + 1;
}
}
// cout << l << " " << r << "\n";
fac min_value = calc(l);
int min_pos = l;
for (int i = l + 1; i <= r; i++) {
if (calc(i) < min_value) {
min_value = calc(i);
min_pos = i;
}
}
cout << (long long)min_value.x << " " << (long long)min_value.y << "\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long tt = 1;
cin >> tt;
while (tt--) solve();
return 0;
}
// g++ -o c++ c++.cpp -O2 -std=c++20 && ./c++
详细
answer.code: In member function ‘void fac::simplify()’: answer.code:13:17: error: ‘gcd’ was not declared in this scope 13 | int g = gcd(x, y); | ^~~