QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629529 | #7735. Primitive Root | 666ldc | WA | 19ms | 3716kb | C++17 | 1.1kb | 2024-10-11 12:58:54 | 2024-10-11 12:58:55 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
using i128 = __int128;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const i64 inf = 2e18;
//-------------------------------------------
void solve()
{
int P, m;
cin >> P >> m;
int mb = 33 - __builtin_clz(P - 1);
int mm = (m >> mb) << mb;
int ans = max((mm - 2) / P, 0LL);
int num = max(((mm - 2) / P), 0LL) * P + 1;
// cerr << ans << " " << num << endl;
while ((num >> mb) <= (mm >> mb))
{
if ((num ^ (P - 1)) <= m)
{
ans++;
}
num += P;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
for (int i = 1; i <= T; i++)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3 2 0 7 11 1145141 998244353
output:
1 2 872
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 5ms
memory: 3648kb
input:
47595 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 2 36 2 37 2 38 2 39 2 40 2 41 2 42 2 43 2 44 2 45 2 46 2 47 2 48 2 49 2 50 2 51 2 52 2 53 2 54 2 55 2 56 2 57 2 58 2 59 2 60...
output:
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 53 ...
result:
ok 47595 lines
Test #3:
score: 0
Accepted
time: 7ms
memory: 3656kb
input:
100000 11 34 71 35 11 45 53 28 3 67 17 38 41 2 23 8 47 26 79 98 89 47 97 33 43 95 97 98 29 79 29 48 67 27 37 3 97 72 71 97 67 53 23 77 71 12 101 92 89 63 61 71 59 94 97 2 29 64 53 74 47 78 67 0 97 66 79 81 3 48 67 87 79 88 59 63 17 25 61 37 67 64 79 93 67 92 89 0 59 88 11 29 29 5 13 47 101 80 3 12 8...
output:
3 1 5 1 23 3 1 0 0 2 1 1 2 2 4 3 1 1 1 2 1 4 0 1 1 3 3 1 3 2 2 0 1 2 16 2 2 2 2 1 1 2 2 0 3 3 1 4 1 4 1 1 14 45 1 1 3 1 4 2 1 2 1 1 2 1 8 2 1 2 1 1 0 1 2 2 1 3 3 9 1 2 1 1 32 1 1 2 1 1 0 1 4 1 1 3 1 2 1 2 2 1 0 2 3 0 1 1 1 3 2 2 1 5 4 1 1 3 2 0 3 2 3 1 6 1 2 9 0 2 2 3 1 1 2 1 2 2 1 1 0 2 2 12 21 4 3...
result:
ok 100000 lines
Test #4:
score: 0
Accepted
time: 11ms
memory: 3708kb
input:
100000 29 83 47 14 29 56 2 29 17 35 67 31 3 24 97 39 17 5 59 16 53 51 29 51 67 72 53 14 79 54 11 35 83 56 89 11 5 70 67 42 89 65 7 40 41 45 79 13 7 26 5 51 5 49 47 46 19 2 89 74 47 27 71 37 37 39 83 86 7 86 71 15 29 94 19 17 101 56 23 3 59 95 97 73 11 15 29 66 23 23 23 51 53 95 11 95 61 0 97 14 73 5...
output:
4 0 3 15 2 1 8 1 1 1 1 3 2 1 1 3 1 1 15 1 1 6 2 0 4 10 10 1 0 1 0 1 2 2 13 1 4 1 1 0 3 1 2 3 2 2 3 9 0 1 1 2 4 0 1 1 2 1 11 2 1 2 3 1 1 1 3 3 1 1 2 1 1 1 1 1 5 8 1 4 9 0 3 1 14 2 1 2 2 1 6 3 1 5 1 1 3 1 2 10 1 2 4 2 1 1 1 1 1 1 4 3 1 5 1 1 2 1 1 1 2 1 6 2 1 0 7 0 1 2 2 4 2 1 1 2 3 1 3 1 1 1 3 1 6 3 ...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 11ms
memory: 3588kb
input:
100000 59 60 97 9 53 69 7 58 71 67 3 88 61 92 83 42 67 64 71 43 29 30 83 31 89 89 47 93 67 90 97 74 11 80 89 84 47 38 19 43 67 55 59 15 101 68 71 58 97 40 73 94 71 88 89 8 67 35 37 81 31 24 23 58 73 51 43 34 71 88 41 69 37 37 7 2 79 79 97 65 17 89 41 78 31 3 97 37 7 91 47 95 97 33 97 60 37 74 29 83 ...
output:
2 1 2 8 1 29 3 1 1 1 2 1 2 2 2 1 8 1 1 3 1 1 1 1 1 2 2 1 1 2 0 3 1 1 2 2 2 0 2 1 6 2 0 1 14 2 1 1 2 4 5 0 5 1 2 1 1 1 0 1 1 0 7 17 2 7 3 1 0 0 1 1 8 3 1 2 1 1 1 1 0 1 1 7 4 2 7 5 0 1 21 3 1 1 0 3 0 0 2 1 1 1 2 5 6 4 1 2 1 1 2 1 4 1 1 2 21 0 3 1 5 1 20 1 2 1 3 5 0 0 6 3 1 2 5 0 1 3 8 2 1 3 1 1 3 1 1 ...
result:
ok 100000 lines
Test #6:
score: 0
Accepted
time: 13ms
memory: 3644kb
input:
100000 1861 3528 2333 9090 2579 5653 8147 4315 1381 1926 1213 8598 7681 7742 5039 8270 7927 3661 2819 9458 7229 4213 683 8300 787 4660 7753 1678 7283 9943 6029 2737 5051 6439 9371 9827 1277 5268 2753 5913 5437 1537 2851 4021 1289 1807 6529 7605 7949 9316 8101 2770 6451 2437 2039 1348 1307 6586 9011 ...
output:
3 4 3 1 2 8 2 2 1 3 1 13 7 1 3 1 2 2 4 2 1 2 2 2 3 1 1 1 5 1 2 1 1 1 1 14 6 4 1 1 1 2 1 1 2 23 1 32 1 2 7 4 1 2 3 1 2 2 4 1 9 1 4 3 4 1 5 3 2 2 4 123 1 2 9 1 1 3 1 1 2 1 3 1 1 4 3 1 1 1 1 1 1 1 1 3 1 1 4 4 1 3 1 18 1 11 1 2 2 1 3 1 1 0 329 1 1 2 3 1 2 1 1 4 1 1 2 4 5 1 3 1 7 2 1 1 2 1 2 2 2 1 1 1 2 ...
result:
ok 100000 lines
Test #7:
score: 0
Accepted
time: 13ms
memory: 3716kb
input:
100000 2861 7238 2411 6690 1951 8793 7877 4503 7237 6677 8311 2550 9883 8304 233 2207 9397 6356 907 7980 7591 192 7643 9101 8963 3945 5683 436 6007 4005 3299 123 1103 5136 9719 9329 2099 1890 7793 6195 2203 8339 4057 9237 5521 3288 6733 7011 563 5121 2879 8277 9091 124 1913 229 307 7781 1801 7702 67...
output:
2 3 6 1 1 1 1 9 1 9 1 2 1 1 1 1 5 1 1 1 4 4 1 2 10 3 1 1 27 5 1 5 1 2 3 2 1 1 22 2 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 18 1 4 11 42 1 3 2 1 2 2 2 1 1 6 1 2 1 1 3 1 1 13 35 1 1 1 1 1 1 3 2 1 1 1 1 7 1 1 1 5 1 1 2 3 1 1 1 1 2 1 1 5 1 4 6 2 1 51 1 1 8 4 3 13 31 5 2 1 50 1 2 1 1 3 19 1 1 2 13 3 1 1 3 1 2 1 ...
result:
ok 100000 lines
Test #8:
score: 0
Accepted
time: 13ms
memory: 3660kb
input:
100000 7177 7208 2753 1599 2909 8176 6547 7781 2543 4318 7177 3366 127 1355 7283 479 6073 6686 3847 195 6761 3446 2099 2392 2609 4676 3637 3268 8849 7603 5179 7731 827 7446 3163 299 9461 8223 6581 8750 4373 9228 9187 8667 2963 6819 4057 7322 5059 9167 9041 3320 9151 8842 2153 6137 1993 6329 4517 606...
output:
2 1 3 2 2 1 12 1 2 1 1 2 2 1 1 2 9 1 1 2 3 1 2 3 2 1 1 3 4 2 2 1 2 1 2 16 1 5 1 1 40 1 1 1 1 30 1 3 2 1 3 3 2 2 4 10 2 9 1 2 1 1 2 1 3 1 1 1 6 2 1 1 2 4 3 1 1 2 1 1 2 2 1 1 2 2 3 1 1 1 1 6 1 2 3 1 6 1 1 2 1 1 1 1 5 2 1 2 2 5 1 3 1 2 2 1 3 47 7 4 1 1 2 1 3 1 1 3 2 2 7 18 1 1 1 1 1 2 5 3 2 1 1 1 1 3 1...
result:
ok 100000 lines
Test #9:
score: 0
Accepted
time: 17ms
memory: 3644kb
input:
100000 22957699 627925429 433183259 202804355 816810829 985631258 54563549 847625650 712837669 860468289 452708161 516705387 541041323 722654987 456499961 122097506 110566411 638241209 103870223 415782860 591063689 459421060 851704643 560244670 491675827 960606500 724808879 813870033 513057607 82205...
output:
27 1 2 15 2 2 2 1 6 5 1 1 3 2 3 4 1 4 1 1 1 1 14 2 1 4 1 1 1 1 1 1 1 1 1 2 2 1 3 1 31 1 1 11 10 1 2 1 1 1 1 1 1 1 2 3 1 1 1 3 2 2 1 3 7 3 1 5 4 2 1 1 2 3 2 1 1 6 2 3 2 1 3 4 2 1 2 3 1 1 2 1 20 1 1 10 9 12 1 1 1 1 1 2 1 1 1 3 2 98 2 1 1 3 1 1 2 7 2 1 1 1 6 1 2 1 1 4 2 1 1 2 1 6 1 1 3 3 2 3 2 1 2 1 1 ...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 17ms
memory: 3640kb
input:
100000 821384891 360483232 94753013 575184250 387876647 758829597 792132637 476022188 535607833 726268124 410858009 781602681 205636231 376470383 645933731 695016569 300304427 613786984 973582219 833018963 29026219 535160021 635806387 1063241 345979391 601446921 785258833 658427991 90922421 44784451...
output:
1 7 2 1 3 3 3 2 3 1 19 1 2 1 5 3 1 1 7 1 2 1 1 10 1 2 2 2 2 1 15 5 1 1 2 1 1 14 1 2 2 1 1 6 1 10 1 3 1 2 1 4 9 1 4 1 1 3 1 582 1 1 1 3 1 5 1 2 2 6 3 2 1 2 1 3 1 1 6 8 1 1 1 3 1 2 1 1 1 1 8 4 2 1 1 1 2 1 1 5 1 1 3 2 1 2 1 2 3 2 1 5 1 1 1 1 1 1 3 1 1 1 2 5 1 1 2 3 1 1 2 1 3 1 1 1 5 1 2 2 1 1 12 1 2 4 ...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 17ms
memory: 3592kb
input:
100000 461078399 442550442 375521033 166102087 604976747 331845816 889534567 570960171 535876871 139282340 31131031 344924738 847344217 802184255 28753481 655216151 866254967 928501728 688120403 888670298 877525879 756867078 356855867 761054248 447231371 477259710 294217477 234719004 964538831 66564...
output:
1 1 1 1 1 11 1 24 2 2 1 3 2 1 1 1 3 7 1 2 1 1 1 1 1 2 3 8 1 1 1 2 2 2 1 1 1 2 4 1 1 1 2 3 9 1 1 1 3 1 5 1 2 4 2 4 1 2 2 2 1 5 1 3 2 4 3 1 1 4 1 1 7 1 1 1 2 1 1 1 1 8 1 3 1 1 2 2 1 3 1 2 1 1 85 1 1 1 2 6 9 3 1 1 2 1 1 1 2 2 4 3 2 2 10 1 1 1 1 3 1 16 12 12 1 2 1 1 6 2 2 6 3 1 1 1 1 2 2 2 1 1 2 1 1 1 2...
result:
ok 100000 lines
Test #12:
score: -100
Wrong Answer
time: 19ms
memory: 3664kb
input:
100000 854620121447 305351081320 465821420627 871311229833 798238974037 704593959229 82347058499 514594072052 78827529281 752873405762 666400710491 526552474252 437289823799 509968252445 301446931481 962983709877 33747912293 818002585949 538211581429 511798563550 750166805383 54533573983 17865394271...
output:
0 2 0 7 9 0 2 4 25 0 0 0 2 2 0 0 0 16 2 2 2 5 2 2 0 5 0 0 6 2 7 2 0 2 0 3 2 2 0 19 3 2 2 0 2 5 7 2 0 2 0 0 0 0 0 0 0 2 2 0 4 0 0 2 2 2 18 0 0 5 0 8 3 0 6 0 2 0 2 17 0 9 2 0 3 2 0 0 4 2 0 2 2 0 2 0 0 0 0 3 0 2 0 10 1 2 0 2 0 3 2 4 0 2 0 0 0 2 0 0 3 26 2 0 2 0 0 27 2 4 2 0 40 0 7 2 0 2 3 2 2 3 0 0 0 3...
result:
wrong answer 1st lines differ - expected: '1', found: '0'