QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111392#6519. X Equals Yhos_lyricAC ✓1627ms9888kbC++143.3kb2023-06-06 22:48:472023-06-06 22:48:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-06 22:48:51]
  • 评测
  • 测评结果:AC
  • 用时:1627ms
  • 内存:9888kb
  • [2023-06-06 22:48:47]
  • 提交

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 <map>
#include <numeric>
#include <queue>
#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; }


pair<Int, Int> solve(const Int X[2], const Int A[2]) {
  if (X[0] == X[1]) {
    return make_pair(2, 2);
  }
  
  // X >= a^2
  {
    vector<pair<vector<Int>, pair<int, Int>>> ps;
    for (int i = 0; i < 2; ++i) {
      for (Int a = 2; a <= A[i] && a * a <= X[i]; ++a) {
        vector<Int> xs;
        for (Int x = X[i]; x; x /= a) {
          xs.push_back(x % a);
        }
        ps.emplace_back(xs, make_pair(i, a));
      }
    }
    sort(ps.begin(), ps.end());
    for (int j = 0; j < (int)ps.size() - 1; ++j) {
      if (ps[j].first == ps[j + 1].first) {
        assert(ps[j].second.first == 0);
        assert(ps[j + 1].second.first == 1);
        return make_pair(ps[j].second.second, ps[j + 1].second.second);
      }
    }
  }
  
  // X < a^2
  // X = u + a v
  const Int DX = X[1] - X[0];
  vector<Int> vs;
  for (Int d = 1; d * d <= DX; ++d) if (DX % d == 0) {
    vs.push_back(d);
    if (d != DX / d) vs.push_back(DX / d);
  }
  for (const Int v : vs) {
    Int lbs[2], ubs[2];
    for (int i = 0; i < 2; ++i) {
      lbs[i] = 2;
      ubs[i] = A[i];
      // 0 <= u <= a-1  <=>  a v <= X <= a (v+1) - 1
      chmax(lbs[i], X[i] / (v + 1) + 1);
      chmin(ubs[i], X[i] / v);
      // 0 <= v <= a-1
      chmax(lbs[i], v + 1);
    }
    const Int diff = DX / v;
    const Int lb = max(lbs[0], lbs[1] - diff);
    const Int ub = min(ubs[0], ubs[1] - diff);
    if (lb <= ub) {
      return make_pair(lb, lb + diff);
    }
  }
  
  return make_pair(-1, -1);
}

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    Int X[2], A[2];
    scanf("%lld%lld%lld%lld", &X[0], &X[1], &A[0], &A[1]);
    
    const bool sw = (X[0] > X[1]);
    if (sw) {
      swap(X[0], X[1]);
      swap(A[0], A[1]);
    }
    auto res = solve(X, A);
    
    if (~res.first) {
      if (sw) {
        swap(res.first, res.second);
      }
      puts("YES");
      printf("%lld %lld\n", res.first, res.second);
    } else {
      puts("NO");
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3716kb

input:

6
1 1 1000 1000
1 2 1000 1000
3 11 1000 1000
157 291 5 6
157 291 3 6
10126 114514 789 12345

output:

YES
2 2
NO
YES
2 10
YES
4 5
NO
YES
6 10

result:

ok correct (6 test cases)

Test #2:

score: 0
Accepted
time: 12ms
memory: 3644kb

input:

1000
920 661 756 534
52 454 31 218
980 77 812 6
729 733 289 660
161 643 21 475
602 525 329 274
782 167 279 113
875 100 388 16
426 498 341 417
433 751 312 39
91 50 47 39
941 388 247 46
725 808 148 486
945 405 700 145
647 509 152 445
45 564 16 468
843 40 530 3
722 36 323 22
568 472 443 41
38 749 25 42...

output:

YES
590 331
YES
14 148
NO
YES
146 147
NO
YES
77 66
YES
26 11
NO
YES
214 286
NO
NO
NO
NO
YES
406 136
YES
96 73
YES
12 185
NO
NO
YES
34 28
YES
10 247
NO
NO
YES
16 5
YES
132 101
NO
YES
701 297
NO
YES
45 174
NO
YES
65 28
NO
NO
YES
89 49
YES
6 5
NO
NO
NO
NO
NO
YES
282 87
NO
YES
170 157
YES
19 27
YES
278 ...

result:

ok correct (1000 test cases)

Test #3:

score: 0
Accepted
time: 376ms
memory: 3820kb

input:

1000
312788 308299 292039 230765
263760 329714 198045 86472
945524 951268 792172 748100
922790 262573 363596 34883
755556 714487 234743 610394
413603 489527 114329 351936
409240 356171 378350 234973
300813 97383 263307 49846
579258 900270 84403 704902
563965 876076 387516 770189
36896 156893 23161 1...

output:

YES
158639 154150
YES
32971 42393
YES
472763 478507
NO
YES
95178 89311
YES
467 521
YES
231155 178086
YES
252122 48692
YES
82752 136254
YES
281983 594094
YES
139 338
YES
36507 35593
YES
14951 31328
YES
332452 120181
YES
714 700
YES
1360 9003
NO
YES
463012 112498
YES
126593 80844
YES
109907 782369
YES...

result:

ok correct (1000 test cases)

Test #4:

score: 0
Accepted
time: 1025ms
memory: 9888kb

input:

1000
981241785 906230829 601363803 626653490
197057696 698550046 128696358 449956015
182548925 796382933 101642956 339324198
816288818 177783961 308532802 32376477
628394197 777548138 355072973 757299936
599075146 752655475 473746059 323396924
261214299 95047810 181049121 60329182
7484303 329571035 ...

output:

YES
528126371 453115415
YES
65685899 316432074
YES
45637232 250248568
YES
146889 31988
YES
314197099 463351040
YES
149768787 200962230
NO
YES
1871076 109233320
YES
1773823 1745826
YES
2336 2447
NO
YES
8104797 7759486
YES
19850328 179385856
YES
5768391 6000362
YES
67503220 115070141
YES
113879578 171...

result:

ok correct (1000 test cases)

Test #5:

score: 0
Accepted
time: 117ms
memory: 3832kb

input:

1000
11131470 5473008 893 586
160457243 377399003 195 363
33293118 10204988 348 650
76153236 165484206 788 591
363322142 108960566 994 862
10849 1346589 861 662
425071 7754389 221 245
5472186 246060285 479 804
699145 16995055 56 861
215170 3080970 423 722
355522 9691597 211 923
24159424 15965332 579...

output:

YES
36 30
YES
50 62
YES
50 37
NO
NO
YES
16 86
YES
28 74
YES
10 19
NO
YES
33 83
YES
16 37
YES
93 81
YES
70 80
NO
YES
50 56
YES
99 29
YES
47 33
YES
2 2
YES
14 77
YES
89 84
YES
42 7
YES
48 93
YES
48 22
YES
63 48
YES
73 96
NO
YES
21 20
YES
36 55
YES
68 24
YES
11 89
YES
36 64
YES
13 34
YES
57 59
YES
65 6...

result:

ok correct (1000 test cases)

Test #6:

score: 0
Accepted
time: 1627ms
memory: 9740kb

input:

1000
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 994905890 324112256 607121052
999502221 99490...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok correct (1000 test cases)