QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #92592 | #144. Primitive root / 原根 | aoui# | 3 | 2ms | 1872kb | C++20 | 938b | 2023-03-30 19:30:20 | 2023-03-30 19:30:24 |
Judging History
answer
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m,nn;
int a[100];
long long fpow(long long x,long long y)
{
long long res=1;
for(;y;y>>=1,x=(__int128)x*x%n)if(y&1)res=(__int128)res*x%n;
return res;
}
int main()
{
scanf("%lld",&n);
if(n==2)
{
puts("1");
return 0;
}
m=nn=n;
for(int i=2;1ll*i*i<=nn;i++)
if(!(nn%i))
{
m=m/i*(i-1);
nn/=i;
a[++a[0]]=i;
while(!(nn%i))nn/=i;
}
if(nn>1)m=m/nn*(nn-1),a[++a[0]]=nn;
if(a[0]>2||(a[1]!=2&&a[0]>1))
{
puts("-1");
return 0;
}
nn=m;
a[0]=0;
for(int i=2;1ll*i*i<=nn;i++)
if(!(nn%i))
{
a[++a[0]]=i;
while(!(nn%i))nn/=i;
}
if(nn>1)a[++a[0]]=nn;
for(int i=2;;i++)
if(__gcd(1ll*i,n)==1)
{
int fl=0;
for(int j=1;j<=a[0];j++)
if(fpow(i,m/a[j])==1)
{
fl=1;
break;
}
if(!fl)
{
printf("%d\n",i);
return 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 1740kb
input:
433
output:
5
result:
ok good solution
Test #2:
score: 0
Accepted
time: 1ms
memory: 1728kb
input:
197
output:
2
result:
ok good solution
Test #3:
score: 0
Accepted
time: 1ms
memory: 1868kb
input:
733
output:
6
result:
ok good solution
Test #4:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
859
output:
2
result:
ok good solution
Test #5:
score: 0
Accepted
time: 1ms
memory: 1696kb
input:
449
output:
3
result:
ok good solution
Test #6:
score: 0
Accepted
time: 1ms
memory: 1680kb
input:
263
output:
5
result:
ok good solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 1732kb
input:
683
output:
5
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 1740kb
input:
17
output:
3
result:
ok good solution
Test #9:
score: 0
Accepted
time: 1ms
memory: 1732kb
input:
359
output:
7
result:
ok good solution
Test #10:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
89
output:
3
result:
ok good solution
Test #11:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
647
output:
5
result:
ok good solution
Test #12:
score: 0
Accepted
time: 1ms
memory: 1732kb
input:
487
output:
3
result:
ok good solution
Test #13:
score: 0
Accepted
time: 1ms
memory: 1712kb
input:
677
output:
2
result:
ok good solution
Test #14:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
829
output:
2
result:
ok good solution
Test #15:
score: 0
Accepted
time: 0ms
memory: 1740kb
input:
227
output:
2
result:
ok good solution
Test #16:
score: 0
Accepted
time: 1ms
memory: 1680kb
input:
151
output:
6
result:
ok good solution
Test #17:
score: 0
Accepted
time: 0ms
memory: 1640kb
input:
607
output:
3
result:
ok good solution
Test #18:
score: 0
Accepted
time: 1ms
memory: 1864kb
input:
661
output:
2
result:
ok good solution
Test #19:
score: 0
Accepted
time: 1ms
memory: 1636kb
input:
151
output:
6
result:
ok good solution
Test #20:
score: 0
Accepted
time: 1ms
memory: 1624kb
input:
101
output:
2
result:
ok good solution
Test #21:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
5
output:
2
result:
ok good solution
Test #22:
score: 0
Accepted
time: 1ms
memory: 1864kb
input:
877
output:
2
result:
ok good solution
Test #23:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
139
output:
2
result:
ok good solution
Test #24:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
389
output:
2
result:
ok good solution
Test #25:
score: 0
Accepted
time: 1ms
memory: 1684kb
input:
421
output:
2
result:
ok good solution
Test #26:
score: 0
Accepted
time: 0ms
memory: 1740kb
input:
709
output:
2
result:
ok good solution
Test #27:
score: 0
Accepted
time: 1ms
memory: 1716kb
input:
331
output:
3
result:
ok good solution
Test #28:
score: 0
Accepted
time: 1ms
memory: 1728kb
input:
269
output:
2
result:
ok good solution
Test #29:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
797
output:
2
result:
ok good solution
Test #30:
score: 0
Accepted
time: 0ms
memory: 1744kb
input:
997
output:
7
result:
ok good solution
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #31:
score: 1
Accepted
time: 1ms
memory: 1872kb
input:
841
output:
2
result:
ok good solution
Test #32:
score: 0
Accepted
time: 0ms
memory: 1628kb
input:
289
output:
3
result:
ok good solution
Test #33:
score: 0
Accepted
time: 1ms
memory: 1708kb
input:
729
output:
2
result:
ok good solution
Test #34:
score: 0
Accepted
time: 1ms
memory: 1676kb
input:
169
output:
2
result:
ok good solution
Test #35:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
961
output:
3
result:
ok good solution
Test #36:
score: 0
Accepted
time: 1ms
memory: 1708kb
input:
31
output:
3
result:
ok good solution
Test #37:
score: 0
Accepted
time: 1ms
memory: 1688kb
input:
243
output:
2
result:
ok good solution
Test #38:
score: 0
Accepted
time: 1ms
memory: 1712kb
input:
625
output:
2
result:
ok good solution
Test #39:
score: 0
Accepted
time: 0ms
memory: 1728kb
input:
121
output:
2
result:
ok good solution
Test #40:
score: 0
Accepted
time: 1ms
memory: 1632kb
input:
125
output:
2
result:
ok good solution
Test #41:
score: -1
Time Limit Exceeded
input:
512
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 1
Accepted
Dependency #1:
100%
Accepted
Test #91:
score: 1
Accepted
time: 0ms
memory: 1684kb
input:
182233
output:
5
result:
ok good solution
Test #92:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
28771
output:
2
result:
ok good solution
Test #93:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
579239
output:
11
result:
ok good solution
Test #94:
score: 0
Accepted
time: 1ms
memory: 1684kb
input:
724747
output:
7
result:
ok good solution
Test #95:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
143513
output:
3
result:
ok good solution
Test #96:
score: 0
Accepted
time: 1ms
memory: 1644kb
input:
695509
output:
2
result:
ok good solution
Test #97:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
999217
output:
5
result:
ok good solution
Test #98:
score: 0
Accepted
time: 1ms
memory: 1868kb
input:
888161
output:
3
result:
ok good solution
Test #99:
score: 0
Accepted
time: 0ms
memory: 1712kb
input:
234287
output:
5
result:
ok good solution
Test #100:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
746483
output:
2
result:
ok good solution
Test #101:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
985003
output:
3
result:
ok good solution
Test #102:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
786959
output:
17
result:
ok good solution
Test #103:
score: 0
Accepted
time: 1ms
memory: 1692kb
input:
1097
output:
3
result:
ok good solution
Test #104:
score: 0
Accepted
time: 1ms
memory: 1868kb
input:
105527
output:
5
result:
ok good solution
Test #105:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
812519
output:
7
result:
ok good solution
Test #106:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
161599
output:
6
result:
ok good solution
Test #107:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
645131
output:
2
result:
ok good solution
Test #108:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
63397
output:
2
result:
ok good solution
Test #109:
score: 0
Accepted
time: 0ms
memory: 1716kb
input:
244429
output:
6
result:
ok good solution
Test #110:
score: 0
Accepted
time: 1ms
memory: 1716kb
input:
911453
output:
2
result:
ok good solution
Test #111:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
340477
output:
2
result:
ok good solution
Test #112:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
28351
output:
6
result:
ok good solution
Test #113:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
414277
output:
2
result:
ok good solution
Test #114:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
411923
output:
2
result:
ok good solution
Test #115:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
986281
output:
19
result:
ok good solution
Test #116:
score: 0
Accepted
time: 1ms
memory: 1648kb
input:
882047
output:
5
result:
ok good solution
Test #117:
score: 0
Accepted
time: 1ms
memory: 1708kb
input:
323009
output:
3
result:
ok good solution
Test #118:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
577153
output:
5
result:
ok good solution
Test #119:
score: 0
Accepted
time: 1ms
memory: 1620kb
input:
42281
output:
11
result:
ok good solution
Test #120:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
601823
output:
5
result:
ok good solution
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
0%
Subtask #7:
score: 1
Accepted
Dependency #4:
100%
Accepted
Test #181:
score: 1
Accepted
time: 1ms
memory: 1744kb
input:
842797909
output:
2
result:
ok good solution
Test #182:
score: 0
Accepted
time: 1ms
memory: 1872kb
input:
662460749
output:
2
result:
ok good solution
Test #183:
score: 0
Accepted
time: 1ms
memory: 1748kb
input:
583578713
output:
3
result:
ok good solution
Test #184:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
714745777
output:
19
result:
ok good solution
Test #185:
score: 0
Accepted
time: 0ms
memory: 1744kb
input:
626528689
output:
7
result:
ok good solution
Test #186:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
848747719
output:
3
result:
ok good solution
Test #187:
score: 0
Accepted
time: 0ms
memory: 1728kb
input:
780868019
output:
2
result:
ok good solution
Test #188:
score: 0
Accepted
time: 0ms
memory: 1840kb
input:
295695817
output:
5
result:
ok good solution
Test #189:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
950964661
output:
6
result:
ok good solution
Test #190:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
219526067
output:
2
result:
ok good solution
Test #191:
score: 0
Accepted
time: 2ms
memory: 1708kb
input:
763440683
output:
2
result:
ok good solution
Test #192:
score: 0
Accepted
time: 0ms
memory: 1708kb
input:
744457559
output:
43
result:
ok good solution
Test #193:
score: 0
Accepted
time: 1ms
memory: 1728kb
input:
117979097
output:
3
result:
ok good solution
Test #194:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
910461493
output:
5
result:
ok good solution
Test #195:
score: 0
Accepted
time: 1ms
memory: 1708kb
input:
796412147
output:
2
result:
ok good solution
Test #196:
score: 0
Accepted
time: 1ms
memory: 1696kb
input:
221019493
output:
2
result:
ok good solution
Test #197:
score: 0
Accepted
time: 0ms
memory: 1740kb
input:
237830497
output:
10
result:
ok good solution
Test #198:
score: 0
Accepted
time: 1ms
memory: 1632kb
input:
209079863
output:
5
result:
ok good solution
Test #199:
score: 0
Accepted
time: 1ms
memory: 1712kb
input:
808345841
output:
3
result:
ok good solution
Test #200:
score: 0
Accepted
time: 1ms
memory: 1716kb
input:
100217503
output:
3
result:
ok good solution
Test #201:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
99546341
output:
2
result:
ok good solution
Test #202:
score: 0
Accepted
time: 1ms
memory: 1736kb
input:
811108069
output:
6
result:
ok good solution
Test #203:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
121875503
output:
5
result:
ok good solution
Test #204:
score: 0
Accepted
time: 1ms
memory: 1716kb
input:
932569537
output:
10
result:
ok good solution
Test #205:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
598983901
output:
6
result:
ok good solution
Test #206:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
54645551
output:
7
result:
ok good solution
Test #207:
score: 0
Accepted
time: 1ms
memory: 1700kb
input:
22252519
output:
3
result:
ok good solution
Test #208:
score: 0
Accepted
time: 1ms
memory: 1744kb
input:
666436031
output:
14
result:
ok good solution
Test #209:
score: 0
Accepted
time: 1ms
memory: 1740kb
input:
900871603
output:
2
result:
ok good solution
Test #210:
score: 0
Accepted
time: 1ms
memory: 1632kb
input:
561111223
output:
43
result:
ok good solution
Subtask #8:
score: 0
Skipped
Dependency #5:
0%
Subtask #9:
score: 0
Skipped
Dependency #6:
0%
Subtask #10:
score: 0
Skipped
Dependency #9:
0%