QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#516868#9167. Coprime Arrayucup-team1198#WA 0ms3812kbC++202.2kb2024-08-12 22:49:362024-08-12 22:49:36

Judging History

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

  • [2024-08-12 22:49:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2024-08-12 22:49:36]
  • 提交

answer

#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}

pair<long long, long long> gcd_extended(long long a, long long b) {
  if (b == 0)
    return make_pair(1, 0);
  long long q = a / b, r = a % b;
  auto tmp = gcd_extended(b, r);
  return make_pair(tmp.second, tmp.first - q * tmp.second);
}

long long solve_kto(vector<pair<long long, long long>> vals) {
  long long m1 = vals[0].first;
  long long r1 = vals[0].second;
  for (int i = 1; i < vals.size(); ++i) {
    long long m2 = vals[i].first;
    long long r2 = vals[i].second;
    auto [a, b] = gcd_extended(m1, m2);
    long long x = (a % m2) * ((r2 - r1) % m2) % m2;
    if (x < 0)
      x += m2;
    r1 += x * m1;
    m1 *= m2;
  }
  return r1;
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  long long s, x;
  cin >> s >> x;
  if (gcd(s, x) == 1) {
    cout << "1\n" << s << '\n';
    return 0;
  }
  vector<pair<long long, int>> primes;
  long long y = x;
  long long i = 2;
  while (i * i <= y) {
    if (y % i == 0) {
      int cnt = 0;
      while (y % i == 0) {
        ++cnt;
        y /= i;
      }
      primes.emplace_back(i, cnt);
    }
    ++i;
  }
  if (y > 1)
    primes.emplace_back(y, 1);
  vector<pair<long long, long long>> vals;
  for (int i = 0; i < primes.size(); ++i) {
    long long q = 1;
    long long p = primes[i].first;
    for (int j = 0; j < primes[i].second; ++j)
      q *= p;
    vals.emplace_back(q, s % p == 1 ? p - 1 : 1);
  }
  if (x % 2 == 0 && s % 2 == 1) {
    vals[0] = make_pair(4, 2);
    long long x = solve_kto(vals);
    cout << 3 << '\n';
    cout << s - x << ' ' << x / 2 << ' ' << x / 2 << '\n';
  } else {
    long long x = solve_kto(vals);
    cout << 2 << '\n';
    cout << s - x << ' ' << x << '\n';
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
-1 5 5

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
13 1

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
851271419 148728581

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
130981163 518576501

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
33396677 1

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
-403356421 225781133 225781133

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
251037077 1

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
30022919 1

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
-564850873 628490171

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
-259201429 167890223 167890223

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
-20295221 30359445 30359445

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
449277308 1

result:

ok Correct

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3612kb

input:

81665969 919836918

output:

3
-1298089409 689877689 689877689

result:

wrong answer Integer element a[1] equals to -1298089409, violates the range [-10^9, 10^9]