Wc2020 guessing game

Title Description

LOJ3330

Topic analysis

If exist $k$ bring $a^k\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$, be $a$ towards $b$ One side .

Then the condition for a point to be selected in a set is that no other point in the set can reach it （ Shrink the ring to a point , The number of schemes to be selected for each ring is $2^{RingBigSmall}-1$）, Then the sum of points selected for all schemes is ${\sum }_{someindividualRing}{2}^{n-(canToreachthisindividualRingOfspotCount)}\ast (2^{RingBigSmall}-1)$

The violence is $O(np)$ Of , It is easy to think of using primitive root optimization .

If $p$ It's an odd prime , Then there is $k$ bring $g^{ak}\equiv g^b(\mathrm{m}\mathrm{o}\mathrm{d}p)$ Equivalent to being $k$ bring $ak\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}\phi (p))$, namely $gcd(a,\phi (p))|b$ .
use BSGS Index seeking , The complexity is $O(n\sqrt{p}+n^2)$.

When $p=q^k$ when , about $(a,q)=1$ You can do it as above , And for $a{q}^b$, Their connecting edges form a DAG, Ride by yourself log It will become 0, No ring , You can do it directly , Complexity $O(n\log p)$

$p$ The algorithm for odd primes can be further optimized , Conditions can be transformed into $gcd(x,\phi (p))|gcd(y,\phi (p))$, And for $g^x\equiv a$, Yes $\text{ord}(a)=\frac{\phi (p)}{gcd(x,\phi (p))}$, $\text{ord(a)}$ yes $a$ The order of , Even if have to $a^k\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ The smallest $k$, Even if have to $xk\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}\phi (p))$ The smallest $k$.

So we just need to find out $\text{ord}(a)$ that will do , because $\text{ord}(a)|\phi (p)$, We can try to divide with the qualitative factor of the latter , Complexity $O(n{\log }^{2}p)$.

Code：

#include<bits/stdc++.h>
#define maxn 5005
using namespace std;
const int mod = 998244353;
int n,p,q,phi,d[35],pw[maxn],ans;
int v1[maxn],s1,v2[maxn],s2,cnt[maxn];
map<int,int>id1,id2;
void Divide(){
    
	for(int i=2;i*i<=q;i++) if(q%i==0) {
    p=i;break;}
	if(!p) p=q;
	int x=phi=q-q/p;
	for(int i=2;i*i<=x;i++) if(x%i==0) {
    d[++*d]=i; while(x%i==0) x/=i;}
	if(x>1) d[++*d]=x;
}
int Pow(int a,int b,int mod){
    int s=1;for(;b;b>>=1,a=1ll*a*a%mod) b&1&&(s=1ll*s*a%mod);return s;}
int ord(int x){
    
	int w=phi;
	for(int i=1;i<=*d;i++)
		while(w%d[i]==0&&Pow(x,w/d[i],q)==1) w/=d[i];
	return w;
}
int main()
{
    
	scanf("%d%d",&n,&q),Divide();
	for(int i=pw[0]=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
	for(int i=1,x;i<=n;i++){
    
		scanf("%d",&x);
		if(x%p==0) v2[++s2]=x,id2[x]=s2;
		else{
    
			x=ord(x);
			if(!id1[x]) id1[x]=++s1,v1[s1]=x;
			cnt[id1[x]]++;
		}
	}
	for(int i=1;i<=s1;i++){
    
		int sum=n;
		for(int j=1;j<=s1;j++) if(v1[j]%v1[i]==0) sum-=cnt[j];
		ans=(ans+1ll*pw[sum]*(pw[cnt[i]]-1))%mod;
	}
	for(int i=1;i<=s2;i++) cnt[i]=n;
	for(int i=1;i<=s2;i++)
		for(int x=v2[i];x;x=1ll*x*v2[i]%q)
			cnt[id2[x]]--;
	for(int i=1;i<=s2;i++) ans=(ans+pw[cnt[i]])%mod;
	printf("%d\n",ans);
}