QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724852#9167. Coprime ArraySunsetGlow95AC ✓0ms3712kbC++141.5kb2024-11-08 15:20:372024-11-08 15:20:38

Judging History

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

  • [2024-11-08 15:20:38]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3712kb
  • [2024-11-08 15:20:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MXP = 30;
int S, X, p(1);
int pms[MXP], pid;

void exgcd(int a, int b, int &x, int &y) {
  if (!b) x = 1, y = 0;
  else exgcd(b, a % b, y, x), y -= a / b * x;
}

int getinv(int a, int b) {
  a %= b;
  int x(0), y(0);
  exgcd(a, b, x, y);
  return (x % b + b) % b;
}

void solve2() {
  int a1(0);
  for (int i(0); i != pid; ++i) {
    if (pms[i] == 2) {
      a1 = p / 2;
      continue;
    }
    int t1(1), t2((S - 1) % pms[i]);
    if (!t2) ++t1;
    a1 = (a1 + t1 * 1LL * getinv(p / pms[i], pms[i]) % p * (p / pms[i])) % p;
  }
  cout << "2\n" << a1 << ' ' << S - a1 << endl;
}
void solve3() {
  int a1(0), a2(0);
  for (int i(0); i != pid; ++i) {
    if (pms[i] == 2) {
      a1 = a2 = p / 2;
      continue;
    }
    int t1(1), t2(1), t3((S - 2) % pms[i]);
    if (!t3) ++t2;
    int coe(getinv(p / pms[i], pms[i]) * 1LL * (p / pms[i]) % p);
    a1 = (a1 + t1 * 1LL * coe) % p;
    a2 = (a2 + t2 * 1LL * coe) % p;
  }
  cout << "3\n" << a1 << ' ' << a2 << ' ' << S - a1 - a2 << endl;
}

inline int gcd(int x, int y) {
  while (y) tie(x, y) = make_pair(y, x % y);
  return x;
}

int main() {
  cin >> S >> X;
  if (gcd(S, X) == 1) cout << "1\n" << S << endl;
  else {
    for (int i(2); i * i <= X; ++i) {
      if (X % i) continue;
      while (X % i == 0) X /= i;
      pms[pid++] = i, p *= i;
    }
    if (X != 1) pms[pid++] = X, p *= X;
    if (pid && pms[0] == 2 && S & 1) solve3();
    else solve2();
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

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: 3568kb

input:

14 34

output:

2
1 13

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
148728581 851271419

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
83981 649473683

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
1 33396677

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
1 18811 48187033

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
1 251037077

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
1 30022919

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
248711 63390587

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
1 1 76579015

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
1 1 40423667

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
1 449277308

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
1 68069 81597899

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
1 470578679

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
1 58450339

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
1 59281 125836831

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
1 381905347

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
1 1 35787883

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed