QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198212 | #6519. X Equals Y | Eason_cyx# | AC ✓ | 121ms | 3856kb | C++14 | 2.1kb | 2023-10-03 09:38:04 | 2023-10-03 09:38:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
long long x, y, A, B;
long long ceil(long long a, long long b) {
return (a + b - 1) / b;
}
// 把 x 的 a 进制表示当成一个 b 进制数
long long gao(long long a, long long b) {
long long ret = 0;
for (long long t = x, p = 1; t; t /= a, p *= b) {
// 注意!t % a >= b 是有可能的,在调用函数的地方检查
ret += p * (t % a);
// 超过 y 就退出,防止溢出
if (ret > y) break;
}
return ret;
}
// 检查 x 的 a 进制和 y 的 b 进制表示是否相等
bool check(long long a, long long b) {
long long xx = x, yy = y;
while (xx && yy) {
if (xx % a != yy % b) return false;
xx /= a; yy /= b;
}
return xx == yy;
}
void solve() {
scanf("%lld%lld%lld%lld", &x, &y, &A, &B);
// 序列长度为 1 的情况
if (x == y) { printf("YES\n2 2\n"); return; }
// 序列长度为 2 的情况
for (long long t = 1; t * t <= max(x, y); t++) if ((y - x) % t == 0) {
long long L = 2, R = A;
L = max(L, ceil(2 * t + x - y, t));
L = max(L, x / (t + 1) + 1);
L = max(L, t + 1);
L = max(L, ((t + 1) * x - y) / (t * (t + 1)) + 1);
L = max(L, (t * t + x - y) / t + 1);
R = min(R, (t * B + x - y) / t);
R = min(R, x / t);
if (L <= R) { printf("YES\n%lld %lld\n", L, (t * L - x + y) / t); return; }
}
// 序列长度为 3 的情况,用双指针判断
for (long long a = 2, b = 2; a * a <= x && a <= A; a++) {
// 把 x 的 a 进制表示当成一个 b 进制数,如果这个数不够 y 说明 b 进制不够大
while (gao(a, b) < y && b * b <= y && b <= B) b++;
if (b * b > y || b > B) break;
// 必须检查两种表示是否真的相等,因为 gao 函数中,x 的 a 进制表示里的某一位可能大于等于 b
if (gao(a, b) == y && check(a, b)) { printf("YES\n%lld %lld\n", a, b); return; }
}
printf("NO\n");
}
int main() {
int T; cin >> T;
while(T--) solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3856kb
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 779 9478
result:
ok correct (6 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3572kb
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 244 246 NO YES 77 66 YES 247 42 NO YES 214 286 NO NO NO NO YES 406 136 YES 96 73 YES 12 185 NO NO YES 45 37 YES 10 247 NO NO YES 193 17 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 146 346 YES...
result:
ok correct (1000 test cases)
Test #3:
score: 0
Accepted
time: 7ms
memory: 3608kb
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 103401 128709 YES 231155 178086 YES 252122 48692 YES 82752 136254 YES 281983 594094 YES 18449 138446 YES 36507 35593 YES 14951 31328 YES 332452 120181 YES 95890 92352 YES 1360 9003 NO YES 463012 112498 YES 126593 80844 YES 10...
result:
ok correct (1000 test cases)
Test #4:
score: 0
Accepted
time: 18ms
memory: 3624kb
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 217080827 245229909 NO YES 8104797 7759486 YES 19850328 179385856 YES 5768391 6000362 YES 67503220 115070141 YES 113...
result:
ok correct (1000 test cases)
Test #5:
score: 0
Accepted
time: 7ms
memory: 3604kb
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: 121ms
memory: 3784kb
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)