QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724762#9167. Coprime ArraySunsetGlow95RE 0ms0kbC++141.2kb2024-11-08 14:57:562024-11-08 14:57:57

Judging History

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

  • [2024-11-08 14:57:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-08 14:57:56]
  • 提交

answer

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

const int MXP = 50;
int S, X, p;
int pms[MXP], pid;

void solve2() {
  int a1(0);
  for (int i(0); i != pid; ++i) {
    if (pms[i] == 2) {
      a1 = 1;
      continue;
    }
    int t1(1), t2((S - 1) % pms[i]);
    if (!t2) ++t1;
    a1 = (a1 + t1 * 1LL * (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 = 1;
      continue;
    }
    int t1(1), t2(1), t3((S - 2) % pms[i]);
    if (!t3) ++t2;
    a1 = (a1 + t1 * 1LL * (p / pms[i])) % p;
    a2 = (a2 + t2 * 1LL * (p / pms[i])) % 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;
    if (pid && pms[0] == 2 && S & 1) solve3();
    else solve2();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

9 6

output:


result: