QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#526382#9167. Coprime Arrayucup-team1264Compile Error//Python32.2kb2024-08-21 14:53:142024-08-21 14:53:14

Judging History

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

  • [2024-08-21 14:53:14]
  • 评测
  • [2024-08-21 14:53:14]
  • 提交

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();
    }
}

Details

  File "answer.code", line 2
    // You said I’d fly away
                 ^
SyntaxError: invalid character '’' (U+2019)