QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#512478 | #9167. Coprime Array | ucup-team4361# | WA | 0ms | 3684kb | C++14 | 2.0kb | 2024-08-10 14:37:49 | 2024-08-10 14:37:49 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define F(i, j, k) for (int i = j; i <= k; ++i)
#define DF(i, j, k) for (int i = j; i >= k; --i)
using namespace std;
template <typename T> inline void read(T &n) {
T w = 1;
n = 0;
char ch = getchar();
while (!isdigit(ch) && ch != EOF) {
if (ch == '-') w = -1;
ch = getchar();
}
while (isdigit(ch) && ch != EOF) {
n = (n << 3) + (n << 1) + (ch & 15);
ch = getchar();
}
n *= w;
}
template <typename T> inline void write(T x) {
T l = 0;
ull y = 0;
if (!x) { putchar(48); return; }
if (x < 0) { x = -x; putchar('-'); }
while (x) { y = y * 10 + x % 10; x /= 10; ++l; }
while (l) { putchar(y % 10 + 48); y /= 10; --l; }
}
template <typename T> inline void writes(T x) {
write(x);
putchar(' ');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
template <typename T> inline void checkmax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void checkmin(T &a, T b) { a = a < b ? a : b; }
inline bool isp(int x) {
for (int i = 2; i * i <= x; i ++)
if (x % i == 0) return false;
return true;
}
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
int s, x;
read(s); read(x);
if (__gcd(s, x) == 1) {
cout << 1 << '\n';
cout << s << '\n';
return 0;
}
if ((s & 1) && !(x & 1)) {
cout << 3 << '\n';
cout << 1 << ' ';
s --;
}
else {
cout << '2' << '\n';
}
int s1 = 1, s2 = 1;
for (int i = 2; i * i <= x; i ++) {
if (x % i != 0) continue;
if (isp(i)) {
if (s % i == 1) s1 *= i;
else s2 *= i;
}
if (i != x / i && isp(x / i)) {
if (s % (x / i) == 1) s1 *= x / i;
else s2 *= x / i;
}
}
cout << (s2 + 1) * s1 << ' ' << s - (s2 + 1) * s1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
9 6
output:
3 1 7 1
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
14 34
output:
2 35 -21
result:
ok Correct
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
1000000000 223092870
output:
2 223092873 776907127
result:
wrong answer Element at position 1 is not coprime to x