QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#549111	#3278. 算术	Flamire^#	26	80ms	4068kb	C++17	1.1kb	2024-09-06 09:03:33	2024-09-06 09:03:34

Judging History

你现在查看的是最新测评结果

[2024-09-06 09:03:34]
评测

测评结果：26
用时：80ms
内存：4068kb

查看

[2024-09-06 09:03:33]
提交

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;
	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 ans=-1;
		for(int k=1;k<=pi;++k)if(qpow(B,k+1)==p-1){ans=k;break;}
		printf("%lld\n",ans);
		// if(res%2==0)
		// {
		// 	if(res==2)printf("2\n"),k=2;
		// 	else printf("%lld\n",res/2-1),k=res/2-1;
		// }
		// else printf("-1\n");
	}
	fclose(stdin);fclose(stdout);return 0;
}

源文件, 语言: C++17

详细

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 4024kb

input:

output:

-1
-1
-1
-1
2
-1
2
-1
-1
-1

result:

ok 10 numbers

Test #2:

score: 5

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok 10 numbers

Test #3:

score: 5

Accepted

time: 0ms

memory: 3764kb

input:

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: 3792kb

input:

output:

-1
-1
2
-1
-1
-1
2
-1
-1
2

result:

ok 10 numbers

Test #5:

score: 5

Accepted

time: 0ms

memory: 4028kb

input:

output:

1
-1
-1
-1
-1
-1
1
-1
-1
-1

result:

ok 10 numbers

Test #6:

score: 5

Accepted

time: 0ms

memory: 4068kb

input:

output:

-1
-1
-1
-1
2
-1
-1
-1
2
-1

result:

ok 10 numbers

Test #7:

score: 5

Accepted

time: 0ms

memory: 3768kb

input:

output:

2
2
2
-1
-1
-1
-1
2
2
-1

result:

ok 10 numbers

Test #8:

score: 5

Accepted

time: 0ms

memory: 3768kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 10 numbers

Test #9:

score: 5

Accepted

time: 0ms

memory: 4068kb

input:

output:

result:

ok 10 numbers

Test #10:

score: 5

Accepted

time: 0ms

memory: 4024kb

input:

output:

1
1
-1
2
-1
-1
1
-1
1
-1

result:

ok 10 numbers

Subtask #3:

score: 5

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #11:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok 100 numbers

Test #12:

score: 5

Accepted

time: 1ms

memory: 3772kb

input:

output:

-1
-1
2
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
2
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
2
-1
2
-1
-1
2
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
2
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1

result:

ok 100 numbers

Test #13:

score: 5

Accepted

time: 0ms

memory: 3848kb

input:

output:

-1
-1
-1
2
-1
2
-1
2
-1
2
26
-1
2
-1
-1
-1
26
26
8
-1
-1
-1
26
-1
26
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
2
26
2
-1
-1
-1
-1
-1
-1
2
2
26
26
2
-1
-1
2
-1
-1
-1
26
-1
-1
26
-1
2
-1
-1
-1
26
-1
-1
26
-1
-1
26
-1
2
-1
8
2
-1
-1
2
-1
-1
-1
-1
-1
26
-1
2
-1
-1
26
-1
-1
26
-1
26
26
-1
2
-1
-1

result:

ok 100 numbers

Test #14:

score: 5

Accepted

time: 0ms

memory: 3772kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
4
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #15:

score: 5

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok 100 numbers

Test #16:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

output:

-1
2
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
2
2
-1
2
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
2
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #17:

score: 5

Accepted

time: 0ms

memory: 4056kb

input:

output:

result:

ok 100 numbers

Test #18:

score: 5

Accepted

time: 0ms

memory: 4056kb

input:

output:

9
-1
-1
9
-1
-1
-1
9
-1
9
-1
-1
1
-1
4
-1
-1
9
2
-1
-1
-1
-1
-1
-1
4
4
-1
-1
2
2
2
-1
-1
4
-1
4
-1
-1
-1
9
-1
9
-1
-1
4
-1
-1
-1
-1
1
-1
4
-1
-1
-1
4
2
-1
-1
9
-1
-1
-1
2
-1
4
2
-1
-1
-1
-1
-1
-1
1
2
2
4
-1
4
9
-1
2
-1
9
-1
-1
-1
9
-1
9
-1
2
4
-1
-1
9
1
-1
-1

result:

ok 100 numbers

Test #19:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Subtask #4:

score: 11

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #20:

score: 11

Accepted

time: 31ms

memory: 3772kb

input:

output:

result:

ok 100 numbers

Test #21:

score: 11

Accepted

time: 21ms

memory: 3772kb

input:

output:

result:

ok 100 numbers

Test #22:

score: 11

Accepted

time: 57ms

memory: 3772kb

input:

output:

result:

ok 100 numbers

Test #23:

score: 11

Accepted

time: 6ms

memory: 3724kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
32
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 100 numbers

Test #24:

score: 11

Accepted

time: 80ms

memory: 4028kb

input:

output:

2
-1
-1
-1
-1
-1
-1
-1
-1
-1
131
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
131
131
-1
2
-1
-1
-1
-1
-1
-1
-1
21
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
131
-1
-1
-1
-1
-1
-1
-1
-1
-1
21
-1
-1
-1
-1
43
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
131
-1
-1
-1
-1

result:

ok 100 numbers

Test #25:

score: 11

Accepted

time: 5ms

memory: 3772kb

input:

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
124
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
124
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
124
-1
-1

result:

ok 100 numbers

Test #26:

score: 11

Accepted

time: 2ms

memory: 3772kb

input:

output:

result:

ok 100 numbers

Test #27:

score: 11

Accepted

time: 45ms

memory: 3768kb

input:

output:

-1
-1
2
-1
-1
-1
-1
2
-1
548
-1
-1
2
-1
-1
-1
-1
-1
182
-1
-1
548
182
-1
-1
182
-1
-1
-1
548
-1
548
182
548
-1
548
-1
-1
-1
-1
-1
182
-1
-1
-1
548
-1
-1
-1
-1
548
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
182
-1
-1
182
182
60
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
182
-1
-1
-1
-1
-1
548
182
18...

result:

ok 100 numbers

Test #28:

score: 11

Accepted

time: 17ms

memory: 3800kb

input:

output:

result:

ok 100 numbers

Test #29:

score: 11

Accepted

time: 28ms

memory: 3776kb

input:

output:

-1
-1
-1
2
2
-1
-1
-1
-1
-1
-1
-1
104
-1
314
34
-1
-1
-1
-1
314
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
20
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
104
2
-1
-1
20
-1
20
104
-1
-1
314
-1
-1
-1
2
62
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
8
-1
-1
-1
-1

result:

ok 100 numbers

Subtask #5:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #30:

score: 0

Time Limit Exceeded

input:

output:

result:

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

Subtask #7:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

Subtask #8:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

Subtask #9:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

Subtask #10:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted