QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584371 | #9381. 502 Bad Gateway | Jiyeon | Compile Error | / | / | C++20 | 3.2kb | 2024-09-23 13:20:57 | 2024-09-23 13:20:57 |
Judging History
你现在查看的是最新测评结果
- [2024-09-24 14:55:37]
- hack成功,自动添加数据
- (/hack/886)
- [2024-09-23 13:20:57]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2024-09-23 13:20:57]
- 提交
answer
#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
int my_gcd(int a, int b) {
return b == 0 ? a : my_gcd(b, a % b);
}
struct fac {
int x, y;
fac(int numerator = 0, int denominator = 1) {
x = numerator;
y = denominator;
simplify();
}
void simplify() {
int g = my_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 end = sqrt(2 * n);
// 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 << (long long) l << " " << (long long) 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";
auto ans = calc(end);
cout << (long long)ans.x << " " << (long long)ans.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 function ‘void solve()’: answer.code:78:19: error: call of overloaded ‘sqrt(__int128)’ is ambiguous 78 | int end = sqrt(2 * n); | ~~~~^~~~~~~ In file included from /usr/include/features.h:461, from /usr/include/x86_64-linux-gnu/c++/13/bits/os_defines.h:39, from /usr/include/x86_64-linux-gnu/c++/13/bits/c++config.h:679, from /usr/include/c++/13/cassert:43, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:33, from answer.code:1: /usr/include/x86_64-linux-gnu/bits/mathcalls.h:143:1: note: candidate: ‘double sqrt(double)’ 143 | __MATHCALL (sqrt,, (_Mdouble_ __x)); | ^~~~~~~~~~ In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:114: /usr/include/c++/13/cmath:442:3: note: candidate: ‘constexpr long double std::sqrt(long double)’ 442 | sqrt(long double __x) | ^~~~ /usr/include/c++/13/cmath:438:3: note: candidate: ‘constexpr float std::sqrt(float)’ 438 | sqrt(float __x) | ^~~~