QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#526385#9167. Coprime Arrayucup-team1264AC ✓0ms3808kbC++202.2kb2024-08-21 14:56:182024-08-21 14:56:19

Judging History

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

  • [2024-08-21 14:56:19]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3808kb
  • [2024-08-21 14:56:18]
  • 提交

answer

// https://www.youtube.com/watch?v=wthasN45KuY
// You said I’d fly away
// But my walls have kept me down
// Now I’m lost and I’m afraid
// And I’m close to hit the ground
// 
// You said I’d fly away
// You said I’d fly anywhere
// But I keep on Falling

#ifndef ONLINE_JUDGE
#include "templates/debug.hpp"
#else
#define debug(...)
#endif

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

// return {gcd(a, b), x, y}.
// x, y is one solution of function ax + by = gcd(a, b);
array<i64, 3> exgcd(i64 a, i64 b) {
    if (!b) return {a, 1, 0};
    auto [g, x, y] = exgcd(b, a % b);
    return {g, y, x - (a / b) * y};
}

// return {x, t} such that for all i, (x + i * t) * a % m = b
// return {-1, -1} if no solution exists.
pair<i64, i64> modEquation(i64 a, i64 b, i64 m) {
    auto [g, t1, _] = exgcd(a, m);
    if (b % g) return {-1, -1};
    i64 x = (b / g) * t1 % (m / g);
    if (x < 0) x += m / g;
    return {x, m / g};
}

// return {r, m} such that x % r = m is equivalent to x % r1 = m1 and x % r2 = m2
// return {-1, -1} if no solution exists.
pair<i64, i64> excrtMerge(i64 r1, i64 m1, i64 r2, i64 m2) {
    auto [d, t1, t2] = exgcd(m1, m2);
    if ((r2 - r1) % d) return {-1, -1};
    i64 m = m1 / d * m2;
    i64 ans = (r1 + ((r2 - r1) / d) * t1 % m2 * m1) % m;
    return {ans < 0 ? ans + m : ans, m};
}

// #define int i64
void solve() {
    int s, x; cin >> s >> x;
    if (gcd(s, x) == 1) {
        cout << 1 << "\n";
        cout << s << "\n";
        return;
    }
    vector<int> ans;
    if (s % 2 == 1 && x % 2 == 0) {
        s--;
        ans.push_back(1);
    }
    i64 r = 0, m = 1;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            int j = 1;
            while (j == s % i) j++;
            tie(r, m) = excrtMerge(r, m, j, i);
        }
    }
    ans.push_back(r); ans.push_back(s - r);
    cout << ans.size() << "\n";
    for (int x: ans) cout << x << " ";
}
#undef int

// Make bold hypotheses and verify carefully
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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

详细

Test #1:

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

input:

9 6

output:

3
1 1 7 

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
1 13 

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
3233231 996766769 

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
1 1 

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
83981 649473683 

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
1 33396677 

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
1 18811 48187033 

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
1 251037077 

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
1 30022919 

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
248711 63390587 

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
1 1 76579015 

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
1 1 40423667 

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
1 449277308 

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
1 2003 81663965 

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
1 470578679 

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
1 58450339 

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
1 59281 125836831 

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
1 381905347 

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
1 1 35787883 

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed