QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515999 | #9167. Coprime Array | hos_lyric | AC ✓ | 0ms | 4068kb | C++14 | 2.2kb | 2024-08-12 13:01:31 | 2024-08-12 13:01:32 |
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")
#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
int main() {
Int S, X;
for (; ~scanf("%lld%lld", &S, &X); ) {
vector<Int> ans;
if (__gcd(S, X) == 1) {
ans = {S};
} else if (!(S % 2 != 0 && X % 2 == 0)) {
for (; ; ) {
// Pr >= (1/2) \prod_p (1 - 2/p)
const Int a = rng() % 1'000'000'000;
if (__gcd(a, X) == 1 && __gcd(S - a, X) == 1) {
ans = {a, S - a};
break;
}
}
} else {
for (; ; ) {
// Pr >= (1/2) \prod_p (1 - 2/p)
const Int a = rng() % 1'000'000'000;
if (__gcd(a, X) == 1 && __gcd(S - 1 - a, X) == 1) {
ans = {1, a, S - 1 - a};
break;
}
}
}
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); ++i) {
if (i) printf(" ");
printf("%lld", ans[i]);
}
puts("");
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4028kb
input:
9 6
output:
3 1 797829289 -797829281
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
14 34
output:
2 977537257 -977537243
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1000000000 223092870
output:
2 648597827 351402173
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
2 1000000000
output:
2 789151703 -789151701
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
649557664 933437700
output:
2 298200317 351357347
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
33396678 777360870
output:
2 730473869 -697077191
result:
ok Correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
48205845 903124530
output:
3 1 137429491 -89223647
result:
ok Correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
251037078 505905400
output:
2 216837617 34199461
result:
ok Correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
30022920 172746860
output:
2 372827647 -342804727
result:
ok Correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
63639298 808058790
output:
2 719666531 -656027233
result:
ok Correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
76579017 362768406
output:
3 1 777684847 -701105831
result:
ok Correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
40423669 121437778
output:
3 1 735432837 -695009169
result:
ok Correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
449277309 720915195
output:
2 343114202 106163107
result:
ok Correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
81665969 919836918
output:
3 1 25779239 55886729
result:
ok Correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
470578680 280387800
output:
2 193319191 277259489
result:
ok Correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
58450340 803305503
output:
2 6128029 52322311
result:
ok Correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
125896113 323676210
output:
3 1 902205133 -776309021
result:
ok Correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
381905348 434752500
output:
2 451597807 -69692459
result:
ok Correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
35787885 270845190
output:
3 1 188604463 -152816579
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed