QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#691480 | #7735. Primitive Root | luoxxx# | WA | 336ms | 3700kb | C++20 | 845b | 2024-10-31 11:36:11 | 2024-10-31 11:36:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int unsigned long long
#define INF 0x3f3f3f3f
const int N=1e5+5;
#define pb push_back
#define pii pair<int,int>
const int mod=998244353;
ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1){ans*=a;ans=ans%mod;}a=a*a;a%=mod;b>>=1;}return ans;}
ll gcd(ll a,ll b){ll t=a%b;while(t){a=b;b=t;t=a%b;}return b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll get_inv(ll x){return ksm(x,mod-2);}
void solve()
{
int p,m;
cin>>p>>m;
if(p==2)
{
cout<<m/2+1<<endl;
return ;
}
int k=m/p;
int ans=k;
for(int i=k;i<=5000;i++)
{
int l=(i*p+1)^(p-1);
if(l<=m)
{ans++;}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int _;cin>>_;while(_--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
3 2 0 7 11 1145141 998244353
output:
1 2 872
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 148ms
memory: 3572kb
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: 327ms
memory: 3640kb
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: 327ms
memory: 3644kb
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: 291ms
memory: 3700kb
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: 323ms
memory: 3652kb
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: 336ms
memory: 3640kb
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: 319ms
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: -100
Wrong Answer
time: 336ms
memory: 3584kb
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:
wrong answer 323rd lines differ - expected: '7264', found: '7262'