QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515999#9167. Coprime Arrayhos_lyricAC ✓0ms4068kbC++142.2kb2024-08-12 13:01:312024-08-12 13:01:32

Judging History

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

  • [2024-08-12 13:01:32]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4068kb
  • [2024-08-12 13:01:31]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#include <chrono>
#ifdef LOCAL
mt19937_64 rng(58);
#else
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif


int main() {
  Int S, X;
  for (; ~scanf("%lld%lld", &S, &X); ) {
    vector<Int> ans;
    if (__gcd(S, X) == 1) {
      ans = {S};
    } else if (!(S % 2 != 0 && X % 2 == 0)) {
      for (; ; ) {
        // Pr >= (1/2) \prod_p (1 - 2/p)
        const Int a = rng() % 1'000'000'000;
        if (__gcd(a, X) == 1 && __gcd(S - a, X) == 1) {
          ans = {a, S - a};
          break;
        }
      }
    } else {
      for (; ; ) {
        // Pr >= (1/2) \prod_p (1 - 2/p)
        const Int a = rng() % 1'000'000'000;
        if (__gcd(a, X) == 1 && __gcd(S - 1 - a, X) == 1) {
          ans = {1, a, S - 1 - a};
          break;
        }
      }
    }
    
    printf("%d\n", (int)ans.size());
    for (int i = 0; i < (int)ans.size(); ++i) {
      if (i) printf(" ");
      printf("%lld", ans[i]);
    }
    puts("");
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
1 797829289 -797829281

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
977537257 -977537243

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
648597827 351402173

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
789151703 -789151701

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
298200317 351357347

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
730473869 -697077191

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
1 137429491 -89223647

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
216837617 34199461

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
372827647 -342804727

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
719666531 -656027233

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
1 777684847 -701105831

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
1 735432837 -695009169

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
343114202 106163107

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
1 25779239 55886729

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
193319191 277259489

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
6128029 52322311

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
1 902205133 -776309021

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
451597807 -69692459

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
1 188604463 -152816579

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed