QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #208179 | #3278. 算术 | 1kri | 10 | 0ms | 3788kb | C++14 | 816b | 2023-10-09 09:13:00 | 2023-10-09 09:13:00 |
Judging History
answer
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int t,p,b;
int c[105],tot;
int phi_p;
int Qpow(int a,int x){
if (x==0)return 1;
int t=Qpow(a,x/2);
t=(__int128)t*t%p;
if (x&1)t=(__int128)t*a%p;
return t;
}
signed main(){
cin>>t>>p;
int _p=p;
for (int i=2;i*i<=p;i++){
while(_p%i==0)c[++tot]=i,_p/=i;
}
if (_p>1)c[++tot]=_p;
phi_p=p;
for (int i=1;i<=tot;i++)
if (i==1||c[i]!=c[i-1])phi_p=phi_p/c[i]*(c[i]-1);
while(t--){
cin>>b;
b%=p;
int k=1,v=(__int128)b*b%p;
while(k<=10&&v!=p-1){
k++;
v=(__int128)b*v%p;
}
if (k<=10)cout<<k<<endl;
else{
int t=phi_p;
for (int i=1;i<=tot;i++)
if (Qpow(b,t/c[i])==1)t/=c[i];
if (Qpow(b,t/2)==p-1)cout<<t/2-1<<endl;
else cout<<-1<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3620kb
input:
10 3 10 7 13 4 17 28 29 13 4 30
output:
-1 -1 -1 -1 2 -1 2 -1 -1 -1
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
10 3 17 21 29 8 25 21 8 14 26 7
output:
2 -1 2 2 -1 -1 2 2 2 -1
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
10 2 14 12 20 12 7 4 6 12 16 13
output:
-1 -1 -1 -1 1 -1 -1 -1 -1 1
result:
ok 10 numbers
Subtask #2:
score: 5
Accepted
Dependency #1:
100%
Accepted
Test #4:
score: 5
Accepted
time: 0ms
memory: 3788kb
input:
10 4 10 10 39 26 20 30 23 13 17 27
output:
-1 -1 2 -1 -1 -1 2 -1 -1 2
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 5 13 45 45 36 46 30 47 6 15 16
output:
1 -1 -1 -1 -1 -1 1 -1 -1 -1
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 6 8 31 37 22 29 7 44 12 29 32
output:
-1 -1 -1 -1 2 -1 -1 -1 2 -1
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
10 7 27 34 12 18 36 57 21 61 27 25
output:
2 2 2 -1 -1 -1 -1 2 2 -1
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
10 8 36 58 52 78 43 42 51 40 18 27
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
10 9 53 26 68 54 24 81 29 13 71 71
output:
2 2 2 -1 -1 -1 2 -1 2 2
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
10 10 67 43 20 39 55 51 47 62 87 100
output:
1 1 -1 2 -1 -1 1 -1 1 -1
result:
ok 10 numbers
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3624kb
input:
100 97 180 581 305 712 315 861 922 484 175 519 943 365 547 142 770 114 182 452 746 290 158 583 185 600 609 412 523 397 227 839 604 387 116 621 914 640 324 678 221 938 709 677 876 678 213 653 581 903 299 287 860 765 672 180 399 907 814 969 934 956 820 864 235 848 815 367 241 737 674 417 856 404 291 4...
output:
-1 2 -1 3 -1 7 -1 2 -1 -1 7 -1 2 -1 5 -1 7 3 -1 2 -1 -1 -1 7 7 -1 -1 -1 3 -1 1 2 -1 -1 -1 -1 3 2 7 -1 -1 -1 -1 2 -1 -1 2 -1 7 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 5 -1 -1 3 -1 -1 -1 -1 2 -1 -1 -1 2 -1 5 1 -1 -1 2 -1 2 -1 -1 -1 3 -1 2 -1 -1
result:
wrong answer 1st numbers differ - expected: '47', found: '-1'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%