QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #861466 | #9981. Collatz Conjecture | ucup-team6275# | AC ✓ | 57ms | 3712kb | C++23 | 2.3kb | 2025-01-18 17:34:15 | 2025-01-18 17:35:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(324);
const ll inf = 1e18;
// ll bin_pow(ll x, ll n, ll mod){
// ll rs = 1;
// for(ll i = 1; i <= n; i *= 2, x = x * x % mod){
// if(n & i){
// rs = rs * x % mod;
// }
// }
// return rs;
// }
ll inv(ll x, ll n) {
x %= n;
if (n == 1) {
return 0;
}
assert(x != 0);
ll val = inv(n % x, x);
ll t = (n * val - 1) / x;
t %= n;
t = -t;
if (t < 0) {
t += n;
}
return t;
}
ll a, b, inv_b;
ll big_step(ll cur) {
if (cur % a == 0) {
return cur / a;
}
ll steps = cur % a * inv_b % a;
steps = -steps;
if (steps < 0) {
steps += a;
}
ll val = cur + steps * b;
assert(val % a == 0);
return val / a;
}
bool stupid_solve(ll n) {
ll iters = 1e6;
ll val = n;
rep(itr, iters) {
if (val % a == 0) {
val /= a;
} else {
val += b;
}
if (val == n) {
return true;
}
}
return false;
}
bool solve(ll n) {
inv_b = inv(b, a);
ll val = big_step(n);
return val <= b;
}
void stress() {
ll c = 0;
while (1) {
cout << ++c << "\n";
a = rnd() % 100 + 2;
b = rnd() % 100 + 1;
while (gcd(a, b) != 1) {
a = rnd() % 100 + 2;
b = rnd() % 100 + 1;
}
ll n = rnd() % 10000;
bool right_rs = stupid_solve(n);
bool my_rs = solve(n);
if (right_rs != my_rs) {
cout << a << " " << b << " " << n << "\n";
break;
}
}
}
int32_t main() {
// stress();
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
ll t;
cin >> t;
rep(itr, t) {
ll n;
cin >> a >> b >> n;
if (solve(n)) {
cout << "Yes" << "\n";
} else {
cout << "No" << "\n";
}
}
return 0;
}
/*
1
1 33 5703
*/
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
7 2 1 1 2 1 2 2 1 3 2 1 100 314 159 265 314 159 2653 314 159 26535
output:
Yes Yes No No Yes Yes No
result:
ok 7 tokens
Test #2:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
100000 123 457 1 123 457 2 123 457 3 123 457 4 123 457 5 123 457 6 123 457 7 123 457 8 123 457 9 123 457 10 123 457 11 123 457 12 123 457 13 123 457 14 123 457 15 123 457 16 123 457 17 123 457 18 123 457 19 123 457 20 123 457 21 123 457 22 123 457 23 123 457 24 123 457 25 123 457 26 123 457 27 123 4...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #3:
score: 0
Accepted
time: 25ms
memory: 3712kb
input:
100000 457 123 1 457 123 2 457 123 3 457 123 4 457 123 5 457 123 6 457 123 7 457 123 8 457 123 9 457 123 10 457 123 11 457 123 12 457 123 13 457 123 14 457 123 15 457 123 16 457 123 17 457 123 18 457 123 19 457 123 20 457 123 21 457 123 22 457 123 23 457 123 24 457 123 25 457 123 26 457 123 27 457 1...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #4:
score: 0
Accepted
time: 14ms
memory: 3584kb
input:
100000 3 100000 1 3 100000 2 3 100000 3 3 100000 4 3 100000 5 3 100000 6 3 100000 7 3 100000 8 3 100000 9 3 100000 10 3 100000 11 3 100000 12 3 100000 13 3 100000 14 3 100000 15 3 100000 16 3 100000 17 3 100000 18 3 100000 19 3 100000 20 3 100000 21 3 100000 22 3 100000 23 3 100000 24 3 100000 25 3 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #5:
score: 0
Accepted
time: 16ms
memory: 3584kb
input:
100000 100000 3 1 100000 3 2 100000 3 3 100000 3 4 100000 3 5 100000 3 6 100000 3 7 100000 3 8 100000 3 9 100000 3 10 100000 3 11 100000 3 12 100000 3 13 100000 3 14 100000 3 15 100000 3 16 100000 3 17 100000 3 18 100000 3 19 100000 3 20 100000 3 21 100000 3 22 100000 3 23 100000 3 24 100000 3 25 10...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #6:
score: 0
Accepted
time: 24ms
memory: 3712kb
input:
100000 1234 567 1 1234 567 2 1234 567 3 1234 567 4 1234 567 5 1234 567 6 1234 567 7 1234 567 8 1234 567 9 1234 567 10 1234 567 11 1234 567 12 1234 567 13 1234 567 14 1234 567 15 1234 567 16 1234 567 17 1234 567 18 1234 567 19 1234 567 20 1234 567 21 1234 567 22 1234 567 23 1234 567 24 1234 567 25 12...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #7:
score: 0
Accepted
time: 22ms
memory: 3584kb
input:
100000 567 1234 1 567 1234 2 567 1234 3 567 1234 4 567 1234 5 567 1234 6 567 1234 7 567 1234 8 567 1234 9 567 1234 10 567 1234 11 567 1234 12 567 1234 13 567 1234 14 567 1234 15 567 1234 16 567 1234 17 567 1234 18 567 1234 19 567 1234 20 567 1234 21 567 1234 22 567 1234 23 567 1234 24 567 1234 25 56...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #8:
score: 0
Accepted
time: 18ms
memory: 3584kb
input:
100000 11 20000 1 11 20000 2 11 20000 3 11 20000 4 11 20000 5 11 20000 6 11 20000 7 11 20000 8 11 20000 9 11 20000 10 11 20000 11 11 20000 12 11 20000 13 11 20000 14 11 20000 15 11 20000 16 11 20000 17 11 20000 18 11 20000 19 11 20000 20 11 20000 21 11 20000 22 11 20000 23 11 20000 24 11 20000 25 11...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #9:
score: 0
Accepted
time: 20ms
memory: 3584kb
input:
100000 20000 11 1 20000 11 2 20000 11 3 20000 11 4 20000 11 5 20000 11 6 20000 11 7 20000 11 8 20000 11 9 20000 11 10 20000 11 11 20000 11 12 20000 11 13 20000 11 14 20000 11 15 20000 11 16 20000 11 17 20000 11 18 20000 11 19 20000 11 20 20000 11 21 20000 11 22 20000 11 23 20000 11 24 20000 11 25 20...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #10:
score: 0
Accepted
time: 14ms
memory: 3584kb
input:
100000 10 9 46 7 10 75 8 5 28 2 9 25 8 3 14 6 1 11 6 7 43 10 1 100 6 7 7 10 9 74 8 9 25 4 7 23 6 5 32 10 7 67 2 5 9 7 2 9 8 3 24 3 10 72 7 8 80 2 9 63 9 4 89 9 7 65 3 2 23 7 4 83 8 7 54 5 2 83 8 7 67 9 8 7 8 3 5 7 2 21 9 10 64 5 1 58 8 9 64 7 6 92 3 7 85 3 4 81 3 7 52 8 3 93 8 3 49 10 3 63 8 5 62 3 ...
output:
No No No No No No No No Yes No No No No No No No Yes No No No No No No No No No No Yes Yes No No No Yes No No No No No No No No No No Yes No Yes No Yes No No No Yes No No Yes No No Yes Yes No No No No No Yes No No No No No No No No No Yes No No No No No No No Yes No No No No No No No No Yes Yes No N...
result:
ok 100000 tokens
Test #11:
score: 0
Accepted
time: 26ms
memory: 3584kb
input:
100000 734 721 305043 803 570 314107 151 173 961985 99 158 637673 223 992 251278 128 675 45643 37 515 402356 920 643 166597 607 246 261024 922 153 82929 963 845 862581 525 898 55977 471 734 239060 401 155 140267 416 587 162998 646 835 165455 115 263 455493 526 965 19267 747 968 848208 485 58 581362 ...
output:
No Yes No No No No No No No No No Yes No No No Yes No Yes No No No No No No Yes No No No No No No No No No Yes No No No No Yes Yes No No No No No No No No No No No No No Yes No No No No No No No Yes No No No Yes No No No No No No No No No No Yes No Yes No Yes No Yes No No No No No Yes No No No No No...
result:
ok 100000 tokens
Test #12:
score: 0
Accepted
time: 35ms
memory: 3584kb
input:
100000 32231 92266 782178617 42230 96003 6217695170 80182 12377 8701700997 31033 52983 6302513359 62119 12786 1119273204 47041 95623 9096117073 31597 62488 6503179735 68149 95382 7983811944 43779 23956 7205672312 42079 13667 8875242043 74808 71447 2510801750 30403 25937 7075700089 23049 52477 533016...
output:
No No No No No No No No No No Yes No No Yes No No No No No No Yes Yes Yes No No No No No No No No No No No No No No No No No Yes No Yes No No No No No No No No No No No No No No No Yes No No No No No No No No Yes No No No No No No No No No No No No No No Yes No Yes No No No Yes No No Yes No No No No...
result:
ok 100000 tokens
Test #13:
score: 0
Accepted
time: 48ms
memory: 3584kb
input:
100000 3810923 5708808 87470435846326 5965262 5386583 90515929776547 3844735 7834949 51374503391657 4252291 1624223 55591304698259 2457933 4620706 97200660986648 7466255 9990183 60765953374093 7441773 6851918 59567739236703 4360951 5147843 30543734215896 6931087 8958551 92447144407682 9382485 798996...
output:
No No No No No Yes No No No Yes Yes No No No No No No No No No No Yes No No No Yes No No No No No No No No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No Yes No No Yes No No No No No No No No No No Yes No No No Yes No No No Yes No No No No No No No No No No No No No ...
result:
ok 100000 tokens
Test #14:
score: 0
Accepted
time: 57ms
memory: 3584kb
input:
100000 461078387 667355286 456090624919430375 23604417 712779052 165726350510651084 847344193 747129143 391621108637132344 423449089 527667332 949130632877632354 688120395 148780459 11178117866347735 934374331 115501564 62664484539924189 420761927 864551062 326392808851216988 558273922 39027397 7738...
output:
No No Yes No Yes No Yes No No Yes No No No No No No No No No No Yes No No No No No Yes No Yes No No No No No No Yes Yes No No No No No No No No No No Yes No No No No No No No No No No No No Yes No No Yes No No No No No No No No No No No No Yes Yes Yes Yes No No Yes No No No No Yes Yes No Yes No No N...
result:
ok 100000 tokens
Test #15:
score: 0
Accepted
time: 16ms
memory: 3584kb
input:
100000 10 9 36 7 10 55 8 5 8 2 9 3 8 3 10 6 1 3 6 7 19 10 1 10 6 7 25 10 9 44 8 9 1 4 7 15 6 5 22 10 7 27 2 5 9 7 2 1 8 3 8 3 10 12 7 8 36 2 9 9 9 4 5 9 7 10 3 2 5 7 4 11 8 7 10 5 2 3 8 7 31 9 8 47 8 3 9 7 2 13 9 10 64 5 1 3 8 9 72 7 6 24 3 7 7 3 4 5 3 7 6 8 3 13 8 3 5 10 3 23 8 5 2 3 8 23 7 10 39 7...
output:
Yes No Yes Yes Yes Yes No Yes No Yes Yes No No No No Yes Yes Yes No Yes Yes Yes No No Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No Yes No Yes No Yes Yes Yes Yes Yes Yes Yes No No No Yes Yes No Yes No Yes No Yes Yes Yes No Yes Yes No No Yes Yes Yes Yes No No Yes Yes No Yes Yes Yes Yes ...
result:
ok 100000 tokens
Test #16:
score: 0
Accepted
time: 26ms
memory: 3584kb
input:
100000 734 721 373447 803 570 401747 151 173 3701 99 158 14869 223 992 51086 128 675 60043 37 515 6261 920 643 45677 607 246 936 922 153 80153 963 845 593941 525 898 188877 471 734 318944 401 155 55627 416 587 191670 646 835 185325 115 263 19083 526 965 498547 747 968 31272 485 58 15152 939 1000 426...
output:
No No Yes No Yes Yes Yes Yes Yes Yes No Yes No No No No No No Yes No No No Yes No Yes No No No No Yes No Yes No No No No No Yes Yes Yes No No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No Yes No No No No No No Yes Yes No Yes Yes No Yes No No No No No Yes No Yes No Yes Yes No No ...
result:
ok 100000 tokens
Test #17:
score: 0
Accepted
time: 35ms
memory: 3712kb
input:
100000 32231 92266 2770604371 42230 96003 1253951600 80182 12377 827385757 31033 52983 1095808654 62119 12786 635278912 47041 95623 2067395761 31597 62488 1652195503 68149 95382 4407733940 43779 23956 562607488 42079 13667 395168791 74808 71447 4494553094 30403 25937 4720828 23049 52477 1130024512 9...
output:
No Yes No No No No No No Yes No No Yes No Yes Yes No No No No No Yes No Yes No No Yes Yes Yes No No No No No Yes No Yes Yes Yes Yes No Yes No No Yes No No Yes No No No No No No No No Yes Yes No Yes No Yes Yes Yes Yes Yes No No No No No No No Yes Yes No Yes Yes No Yes No Yes No No Yes Yes No No Yes N...
result:
ok 100000 tokens
Test #18:
score: 0
Accepted
time: 47ms
memory: 3712kb
input:
100000 3810923 5708808 14932360854078 5965262 5386583 22172020281391 3844735 7834949 5127417513547 4252291 1624223 3450294524379 2457933 4620706 1312190182588 7466255 9990183 67111186895123 7441773 6851918 16109177647669 4360951 5147843 21136086794083 6931087 8958551 8615586618510 9382485 7989964 42...
output:
Yes No Yes No No No Yes No Yes Yes Yes Yes No No Yes No Yes No No Yes Yes Yes Yes No Yes No No Yes No No No No No No No No Yes Yes No Yes Yes Yes Yes Yes No No No Yes Yes No Yes Yes Yes Yes No No Yes No No Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes No Yes No Yes No No No Yes No No No No Yes Yes Ye...
result:
ok 100000 tokens
Test #19:
score: 0
Accepted
time: 56ms
memory: 3584kb
input:
100000 461078387 667355286 302028648423356735 23604417 712779052 533021022937096 847344193 747129143 161639078989616557 423449089 527667332 22482850933355366 688120395 148780459 25626397068165945 934374331 115501564 19049475390517885 420761927 864551062 272293012993870622 177609799 212880817 1464426...
output:
No Yes Yes Yes Yes No No Yes Yes No No No Yes Yes Yes No Yes No No No Yes Yes No No No Yes Yes No No Yes No Yes Yes Yes No Yes No No No Yes Yes No Yes No Yes Yes Yes No No Yes No No Yes No No Yes Yes No Yes No No Yes No No Yes No No No No Yes No No No No Yes No No Yes No Yes Yes Yes Yes No No No Yes...
result:
ok 100000 tokens
Test #20:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1000000000 1 1000000000000000000
output:
No
result:
ok "No"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
1 3 1000000000 1000000000000000000
output:
No
result:
ok "No"
Extra Test:
score: 0
Extra Test Passed