QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549113 | #3278. 算术 | Flamire# | 0 | 1ms | 3708kb | C++17 | 1.1kb | 2024-09-06 09:10:04 | 2024-09-06 09:10:05 |
answer
#include <bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
int t;ll p;
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll phi(ll x)
{
ll ans=x;
for(int i=2;1ll*i*i<=x;++i)if(x%i==0)
{
ans=ans/i*(i-1);
while(x%i==0)x/=i;
}
if(x!=1)ans=ans/x*(x-1);
return ans;
}
map<ll,int> mp;
ll qpow(ll bs,ll ex){ll ans=1;while(ex){if(ex&1)ans=(lll)ans*bs%p;bs=(lll)bs*bs%p;ex>>=1;}return ans;}
int main()
{
scanf("%d%lld",&t,&p);ll pi=phi(p),tpi=pi;//printf("pi:%lld\n",pi);
for(int i=2;1ll*i*i<=pi;++i)
{
while(pi%i==0)++mp[i],pi/=i;
}
if(pi!=1)++mp[pi];
pi=tpi;
while(t--)
{
ll B;scanf("%lld",&B);
if(gcd(B,p)!=1){printf("-1\n");continue;}
ll res=pi;
for(auto x:mp)
{
while(res%x.first==0&&qpow(B,res/x.first)==1)res/=x.first;
}
ll k;
// ll ans=-1;
// for(int k=1;k<=pi;++k)if(qpow(B,k+1)==p-1){ans=k;break;}
// printf("%lld\n",ans);
// printf("res:%lld\n",res);
if(res%2==0&&qpow(B,res/2)==p-1)
{
if(res==2)printf("2\n"),k=2;
else printf("%lld\n",res/2-1),k=res/2-1;
}
else printf("-1\n");
// putchar(10);
}
fclose(stdin);fclose(stdout);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3704kb
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: 5
Accepted
time: 1ms
memory: 3708kb
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
Wrong Answer
time: 0ms
memory: 3704kb
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:
wrong answer 5th numbers differ - expected: '1', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
0%