QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#516918#9167. Coprime Arrayucup-team1198#AC ✓0ms3848kbC++203.1kb2024-08-13 00:04:272024-10-14 07:52:37

Judging History

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

  • [2024-10-14 07:52:37]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:0ms
  • 内存:3848kb
  • [2024-08-13 00:04:27]
  • 评测
  • 测评结果:100
  • 用时:0ms
  • 内存:3856kb
  • [2024-08-13 00:04:27]
  • 提交

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

const long long INF = 1'000'000'000;

vector<long long> solve(long long s, long long x) {
  if (gcd(s, x) == 1)
    return {s};
  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);
  while (true) {
    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;
      long long r = s % p;
      if (p == 2) {
        r = 1;
      } else {
        while (s % p == r) {
          r = 1 + rand() % (p - 1);
        }
      }
      vals.emplace_back(q, r);
    }
    if (x % 2 == 0 && s % 2 == 1) {
      vals[0] = make_pair(4, 2);
      long long t = solve_kto(vals);
      if (abs(s - t) <= INF)
        return {s - t, t / 2, t / 2};
    } else {
      long long t = solve_kto(vals);
      return {s - t, t};
    }
  }
}

//#define DEBUG

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

#ifdef DEBUG
  for (long long s = 2; s <= INF; ++s) {
    for (long long x = 2; x <= INF; ++x) {
      auto ans = solve(s, x);
      bool ok = true;
      long long real = 0;
      for (long long y : ans) {
        ok = ok && abs(gcd(y, x)) == 1 && abs(y) <= INF;
        real += y;
      }
      ok = ok && real == s;
      if (!ok) {
        cerr << "BUG!!\n";
        cerr << s << ' ' << x << '\n';
        for (long long y : ans)
          cerr << y << ' ';
        cerr << '\n';
      }
    }
  }
#else
  long long s, x;
  cin >> s >> x;
  auto ans = solve(s, x);
  cout << ans.size() << '\n';
  long long kek = 0;
  for (long long y : ans) {
    cout << y << ' ';
    kek += y;
  }
  cout << '\n';
#endif
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

9 6

output:

3
7 1 1 

result:

ok Correct

Test #2:

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

input:

14 34

output:

2
-11 25 

result:

ok Correct

Test #3:

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

input:

1000000000 223092870

output:

2
918513017 81486983 

result:

ok Correct

Test #4:

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

input:

2 1000000000

output:

2
-361328127 361328129 

result:

ok Correct

Test #5:

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

input:

649557664 933437700

output:

2
403418111 246139553 

result:

ok Correct

Test #6:

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

input:

33396678 777360870

output:

2
-669147599 702544277 

result:

ok Correct

Test #7:

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

input:

48205845 903124530

output:

3
-612651953 330428899 330428899 

result:

ok Correct

Test #8:

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

input:

251037078 505905400

output:

2
163516949 87520129 

result:

ok Correct

Test #9:

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

input:

30022920 172746860

output:

2
-90919249 120942169 

result:

ok Correct

Test #10:

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

input:

63639298 808058790

output:

2
-63019009 126658307 

result:

ok Correct

Test #11:

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

input:

76579017 362768406

output:

3
-500800805 288689911 288689911 

result:

ok Correct

Test #12:

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

input:

40423669 121437778

output:

3
-13291505 26857587 26857587 

result:

ok Correct

Test #13:

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

input:

449277309 720915195

output:

2
358841386 90435923 

result:

ok Correct

Test #14:

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

input:

81665969 919836918

output:

3
-409437221 245551595 245551595 

result:

ok Correct

Test #15:

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

input:

470578680 280387800

output:

2
422847727 47730953 

result:

ok Correct

Test #16:

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

input:

58450340 803305503

output:

2
-137168351 195618691 

result:

ok Correct

Test #17:

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

input:

125896113 323676210

output:

3
-285273509 205584811 205584811 

result:

ok Correct

Test #18:

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

input:

381905348 434752500

output:

2
56698471 325206877 

result:

ok Correct

Test #19:

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

input:

78916498 653897673

output:

1
78916498 

result:

ok Correct

Test #20:

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

input:

35787885 270845190

output:

3
-180941513 108364699 108364699 

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed