QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512478#9167. Coprime Arrayucup-team4361#WA 0ms3684kbC++142.0kb2024-08-10 14:37:492024-08-10 14:37:49

Judging History

This is the latest submission verdict.

  • [2024-08-11 17:38:28]
  • hack成功,自动添加数据
  • (/hack/775)
  • [2024-08-10 14:37:49]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3684kb
  • [2024-08-10 14:37:49]
  • Submitted

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