QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#512577#9167. Coprime Arrayucup-team4361#AC ✓0ms3716kbC++142.7kb2024-08-10 14:59:422024-10-14 07:52:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 07:52:01]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:0ms
  • 内存:3716kb
  • [2024-08-11 17:38:28]
  • hack成功,自动添加数据
  • (/hack/775)
  • [2024-08-10 14:59:44]
  • 评测
  • 测评结果:100
  • 用时:1ms
  • 内存:3692kb
  • [2024-08-10 14:59:42]
  • 提交

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) {
    if (x == 1) return false;
    for (int i = 2; i * i <= x; i ++)
        if (x % i == 0) return false;
    return true;
}

inline int ksm(int x, int y, int z) {
    int k = 1;
    while (y) {
        if (y & 1) k = (LL)k * x % z;
        x = (LL)x * x % z;
        y >>= 1;
    }
    return k;
}

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 ss = 1;
    for (int i = 1; i * i <= x; i ++) {
        if (x % i != 0) continue;
        if (isp(i)) {
            ss *= i;
        }
        if (i != x / i && isp(x / i)) {
            ss *= (x / i);
        }
    }
    int X = 0;
    for (int i = 1; i * i <= x; i ++) {
        if (x % i != 0) continue;
        if (isp(i)) {
            if (s % i != 1) X = (X + (LL)(ss / i) * ksm(ss / i, i - 2, i) % ss) % ss;
            else X = (X + ss - (LL)(ss / i) * ksm(ss / i, i - 2, i) % ss) % ss;
        }
        if (i != x / i && isp(x / i)) {
            if (s % (x / i) != 1) X = (X + (LL)(ss / (x / i)) * ksm(ss / (x / i), x / i - 2, x / i) % ss) % ss;
            else X = (X + ss - (LL)(ss / (x / i)) * ksm(ss / (x / i), (x / i) - 2, (x / i)) % ss) % ss;
        }
    }
    cout << X << ' ' << s - X << '\n';
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

9 6

output:

3
1 1 7

result:

ok Correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

14 34

output:

2
1 13

result:

ok Correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

1000000000 223092870

output:

2
148728581 851271419

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

649557664 933437700

output:

2
83981 649473683

result:

ok Correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

33396678 777360870

output:

2
1 33396677

result:

ok Correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

48205845 903124530

output:

3
1 6271 48199573

result:

ok Correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

251037078 505905400

output:

2
1 251037077

result:

ok Correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

30022920 172746860

output:

2
1 30022919

result:

ok Correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

63639298 808058790

output:

2
248711 63390587

result:

ok Correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

76579017 362768406

output:

3
1 1 76579015

result:

ok Correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

40423669 121437778

output:

3
1 1 40423667

result:

ok Correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

449277309 720915195

output:

2
1 449277308

result:

ok Correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

81665969 919836918

output:

3
1 68069 81597899

result:

ok Correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

470578680 280387800

output:

2
1 470578679

result:

ok Correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

58450340 803305503

output:

2
1 58450339

result:

ok Correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

125896113 323676210

output:

3
1 44461 125851651

result:

ok Correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

381905348 434752500

output:

2
1 381905347

result:

ok Correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

35787885 270845190

output:

3
1 1 35787883

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed