QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73539 | #5272. Greatest Common Divisor | sinbad | WA | 310ms | 29276kb | C++ | 4.7kb | 2023-01-25 17:04:11 | 2023-01-25 17:04:12 |
Judging History
answer
// #define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
constexpr inline int lg2(int64 x) { return x == 0 ? -1 : sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
constexpr inline int p2ceil(int64 x) { return 1 << (lg2(x - 1) + 1); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
inline void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
inline int mod(int x) { return x >= MOD ? x - MOD : x; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
int main() {
int n, q;
cin >> n >> q;
auto solve =
[&](int x, int y) {
while (y > 0) {
int z = x / y;
x = y;
y = z;
}
return x;
};
vector<array<int, 3>> can;
for (int y = 1; y <= n; ++y) {
for (int q = 0, m = 0; m <= n; ++q, m += y) {
if (y == 1 && q == 1) continue;
int g = solve(y, q);
if (y % g == 0) can.push_back({y, q, g});
}
}
// trace(SZ(can));
// trace(can);
vector<ii> ret;
for (auto [y, q, g] : can) {
int R = min(y * (q + 1), n + 1);
for (int x = y * q; x < R; x += g) {
if (x > 0 && gcd(x, y) == g) ret.push_back({x, y});
}
}
sort(ret.begin(), ret.end());
// trace(SZ(ret));
trace(ret);
while (q--) {
int k;
cin >> k;
--k;
if (k >= SZ(ret)) {
cout << -1 << " " << -1 << '\n';
} else {
cout << ret[k].first << " " << ret[k].second << '\n';
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3320kb
input:
10 13 1 2 3 4 5 6 7 8 9 10 11 12 13
output:
2 2 3 3 4 2 4 4 5 5 6 6 7 7 8 8 9 3 9 9 10 4 10 10 -1 -1
result:
ok 26 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
1 1 1
output:
-1 -1
result:
ok 2 number(s): "-1 -1"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
5 100 2 20 17 14 23 19 8 10 21 19 16 16 19 16 6 11 9 12 5 12 21 8 15 5 24 5 5 17 6 12 1 21 25 3 20 8 7 11 15 8 6 1 16 25 14 1 11 13 11 20 6 2 5 7 3 6 19 20 3 22 21 11 13 18 18 14 2 1 19 3 20 23 3 16 1 8 14 16 11 9 10 17 22 3 8 12 2 12 9 5 18 6 9 25 6 12 19 14 16 6
output:
3 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 5 -1 -1 -1 -1 -1 -1 -1 -1 5 5 -1 -1 5 5 5 5 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 -1 -1 -1 2 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 5 5 -1 -...
result:
ok 200 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
20 100 289 374 235 204 189 215 84 194 242 331 216 326 264 113 181 344 124 91 39 189 256 77 228 155 201 52 386 31 384 397 267 282 226 249 400 208 48 176 131 296 288 266 75 367 298 311 388 165 11 121 44 269 325 293 392 210 365 150 221 365 188 298 23 192 223 179 245 286 103 118 314 352 394 255 78 225 4...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 4 -1 -1 -...
result:
ok 200 numbers
Test #5:
score: 0
Accepted
time: 4ms
memory: 3356kb
input:
100 10000 6612 4694 4970 8529 7165 1355 9979 3049 2281 9998 5330 6674 5280 7838 729 810 5836 1465 5805 5812 5933 9493 7134 2581 3173 9673 2322 2776 3053 1377 9601 1547 1902 93 3114 5408 7577 8994 8173 189 6672 3431 2832 4764 6650 6842 379 7307 1283 7753 6203 1229 1849 297 9026 6520 9568 4419 5093 81...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 57 57 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 20000 numbers
Test #6:
score: 0
Accepted
time: 42ms
memory: 3476kb
input:
1000 200000 134451 18536 303685 537674 428477 446829 583452 904095 295077 864453 949776 744108 144837 500318 596486 214710 338668 667766 679253 603928 158044 947810 272203 572606 767501 295561 508775 629483 950313 206695 394144 959539 932878 230667 676892 318913 642959 274136 662458 834771 792627 36...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 400000 numbers
Test #7:
score: 0
Accepted
time: 60ms
memory: 4424kb
input:
10000 200000 2655653 24587357 25148377 40766601 43392625 53598135 20747785 35410107 39405761 58571003 50359654 79351089 20229583 11737455 91700105 75175779 26082486 26421724 51374385 2587276 15213302 69282831 73995969 38365995 37916148 97717081 11920317 64165764 28306295 40932112 94352977 55672605 1...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 400000 numbers
Test #8:
score: -100
Wrong Answer
time: 310ms
memory: 29276kb
input:
100000 200000 9900160421 1838711025 7215006831 4873988367 736988586 8927878267 9133829796 7556948229 1897988856 5049034409 4778625059 5483590472 2534396502 9316515227 4739195532 5161682788 8724411871 3977298661 9241212439 3737115542 1478991748 4568993297 2152062989 9851759441 1147444104 8871096091 8...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
wrong answer 33385th numbers differ - expected: '43445', found: '-1'