Original root and NTT 5000 word explanation

Euler theorem

if m,a Coprime be   

The concept of order

if a,m Coprime , bring Minimum Positive integer n be called a model m Order in sense , Write it down as

The concept of primitive root

if , namely a The order of is equal to m The Euler function of , said a For the root

Properties of order

        In the mold m Two are different in the sense , Then it starts to enter the cycle

Order periodicity

    That is, the same two indices in the sense of modular order , Corresponding mod m The idempotent under is also the same

  That is, the order is the factor of Euler function

Primitive root existence theorem

Only module 2,4, Only then exists the original root , among p Is odd , Prime number , That is, odd prime numbers

Judgement theorem of primitive root

set up m>1,g As a positive integer , And g,m Coprime ,g yes m If and only if , All prime factors of qi

All satisfied with

The minimum primitive root solves all primitive roots

In finding the smallest primitive root p Under the circumstances , p^k Just need to satisfy  

Solve the original root template

First step Euler screen Preprocess all in the range Prime number , as well as Euler function , Primitive root existence

Based on Primitive root existence theorem

 phi[1]=1;

    for(int i=2;i<=N;i++)
    {
        if(!not_prime[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;

        }
        for(int j=1;j<=tot&&prime[j]*i<=N;j++)
        {
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];

                break;

            }

            phi[i*prime[j]]=phi[i]*(prime[j]-1);

        }
    }

rt[2]=rt[4]=1;

    for(ll i=2;i<=tot;i++)
    {


        for(ll j=1;j*prime[i]<=N;j*=prime[i])
        {
            rt[j*prime[i]]=1;

        }

         for(ll j=2;j*prime[i]<=N;j*=prime[i])
        {
            rt[j*prime[i]]=1;

        }
    }

The second step , Read in the judgment number , First, judge whether there is a primitive root , Some words , For its Euler function is decomposed into prime factors , As the basis for judging the rationality of the original root

void oula(int  x)
{
    len=0;

    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            temp[++len]=i;

            while(x%i==0)
                x/=i;

        }
    }

    if(x>1)
        temp[++len]=x;

    return ;

}

The third step , Enumerate the minimum primitive root , The minimum original root value is usually very small , You can directly enumerate . According to the original root definition , Its order is phi[p], The basis of judgment is its phi[p] The power should be mod m =1. Then we can't just meet this condition to judge phi[p] Is its order , It also needs to be Primitive root decision theorem , Enumerate the factors after the prime factor decomposition of Euler function ,x The Euler function of divided by the power of the factor is mod m It cannot be equal to 1.

bool check(ll x,ll p)
{
    if(qp(x,phi[p],p)!=1)
        return 0;

    for(int i=1;i<=len;i++)
    {
        if(qp(x,phi[p]/temp[i],p)==1)
            return 0;

    }

    return 1;

}

ll findmin(int p)
{
    for(int i=1;i<p;i++)
    {
        if(check(i,p))
            return i;

    }

    return 0;

}

Step four , Find the smallest primitive root , Enumerate the smallest primitive root k The next power , Satisfy  gcd(k,phi[p])=1 Talent

void getrt(int p,int x)
{
   ll pp=1;

   lenans=0;


   for(ll i=1;i<=phi[p];i++)
   {
       pp=pp*x%p;

       if(gcd(i,phi[p])==1)
        ans[++lenans]=pp;

   }

   return ;

}

【 Templates 】 Primordial root - Luogu

# include<iostream>
# include<algorithm>
using namespace std;

const int N =1000000;

typedef long long int ll;

ll phi[N],prime[N],rt[N];

int tot;

bool not_prime[N];
void init()
{
    phi[1]=1;

    for(int i=2;i<=N;i++)
    {
        if(!not_prime[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;

        }
        for(int j=1;j<=tot&&prime[j]*i<=N;j++)
        {
            not_prime[prime[j]*i]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];

                break;

            }

            phi[i*prime[j]]=phi[i]*(prime[j]-1);

        }
    }

    rt[2]=rt[4]=1;

    for(ll i=2;i<=tot;i++)
    {


        for(ll j=1;j*prime[i]<=N;j*=prime[i])
        {
            rt[j*prime[i]]=1;

        }

         for(ll j=2;j*prime[i]<=N;j*=prime[i])
        {
            rt[j*prime[i]]=1;

        }
    }

    return  ;


}

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);

}
ll qp(ll base, ll pow, ll mod)
{

    ll ans=1;

    while(pow)
    {
        if(pow&1)
            ans=ans*base%mod;

        pow>>=1;

        base=base*base%mod;

    }

    return ans;

}

ll temp[N];
int len;

void oula(int  x)
{
    len=0;

    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            temp[++len]=i;

            while(x%i==0)
                x/=i;

        }
    }

    if(x>1)
        temp[++len]=x;

    return ;

}

bool check(ll x,ll p)
{
    if(qp(x,phi[p],p)!=1)
        return 0;

    for(int i=1;i<=len;i++)
    {
        if(qp(x,phi[p]/temp[i],p)==1)
            return 0;

    }

    return 1;

}

ll findmin(int p)
{
    for(int i=1;i<p;i++)
    {
        if(check(i,p))
            return i;

    }

    return 0;

}
int lenans=0;

ll ans[N];

void getrt(int p,int x)
{
   ll pp=1;

   lenans=0;


   for(ll i=1;i<=phi[p];i++)
   {
       pp=pp*x%p;

       if(gcd(i,phi[p])==1)
        ans[++lenans]=pp;

   }

   return ;

}
int main ()
{


  init();

  int t;

  cin>>t;

  while(t--)
  {
      int p,mod;
      cin>>p>>mod;

      if(rt[p])
      {
          oula(phi[p]);

          int mn=findmin(p);


          getrt(p,mn);

          sort(ans+1,ans+lenans+1);


          cout<<lenans<<'\n';

          for(int i=1;i<=lenans/mod;i++)
          {
              cout<<ans[i*mod]<<" ";
          }

          cout<<'\n';



      }
      else
      {
          cout<<0<<'\n';

          cout<<'\n';


      }
  }

}

NTT Templates

inline void ntt(int a[],int len,int inv)
{
	int bit=0;
	while ((1<<bit)<len)++bit;
	fo(i,0,len-1)
	{
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		if (i<rev[i])swap(a[i],a[rev[i]]);
	}// Front and FFT equally 
	for (int mid=1;mid<len;mid*=2)
	{
		int tmp=pow(g,(mod-1)/(mid*2));// The original root replaces the unit root 
		if (inv==-1)tmp=pow(tmp,mod-2);// The inverse transformation is multiplied by the inverse element 
		for (int i=0;i<len;i+=mid*2)
		{
			int omega=1;
			for (ll j=0;j<mid;++j,omega=omega*tmp%mod)
			{
				int x=a[i+j],y=omega*a[i+j+mid]%mod;
				a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;// Pay attention to the mold 
			}
		}// In general, and FFT almost 
	}
}

  The generating function is well set , The only detail is vector Setting of container subscript , Here the 0 representative 1, In the process of operation , The error also produces a subscript offset

such as v1[0] representative 1,v1[1] representative 2

v2[0] representative 1,v2[1] representative 2

Do an operation

v1[0]=v1[0]*v2[0] in other words ,v1[0] On behalf of 2

v1[1] On behalf of 3

Conduct m Times operation

v[pos] representative pos+1+m-1 =pos+m

So the final answer should be output v[][k-m]

# include<iostream>
# include<vector>
# include<cstdio>
# include<cstring>
# include<queue>
# include<algorithm>
# include<cmath>
using namespace std;
typedef long long int ll;
const int N=100010;
# define mod 998244353
int s[N];
ll fac[N],inv[N];

ll qp(ll base ,ll pow)
{
    ll ans=1;

    while(pow)
    {
        if(pow&1)
            ans=ans*base%mod;

        base=base*base%mod;

        pow>>=1;

    }

    return ans;

}
void init()
{
    fac[0]=1;

    for(int i=1;i<N;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }

    inv[N-1]=qp(fac[N-1],mod-2);

    for(int i=N-2;i>=0;i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;

    }
}

ll C(int n,int k)
{
    if(k>n)
        return  0;

    return fac[n]*inv[k]%mod*inv[n-k]%mod;

}



int rev[N*2];

void init1(int k)
{
    int len=(1<<k);

    for(int i=0;i<len;i++)
        rev[i]=0;

    for(int i=0;i<len;i++)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
    }
    return ;

}

void NTT(vector<ll>&a,int n,int flag)
{

    for(int i=0;i<n;i++)
    {
        if(i<rev[i])
        {
            swap(a[i],a[rev[i]]);

        }
    }

    for(int h=1;h<n;h<<=1)
    {
        ll gn=qp(3ll,(mod-1)/(h*2));

        if(flag==-1)
            gn=qp(gn,mod-2);


        for(int j=0;j<n;j+=(h*2))
        {

            ll g=1;

            for(int k=j;k<j+h;k++)
            {

                ll x=a[k];

                ll y=g*a[k+h];

                a[k]=(x+y)%mod;

                a[k+h]=((x-y)%mod+mod)%mod;

                g=g*gn%mod;


            }
        }
    }

    if(flag==-1)
    {
        ll t=qp(n,mod-2);

        for(int i=0;i<n;i++)
        {
            a[i]=a[i]*t%mod;

        }
    }

    return ;

}

void mul(vector<ll>&a,vector<ll>&b,int siz)
{

    int k=1,s=2;

    while((1<<k)<siz-1)
    {
        s<<=1;
        k++;

    }

    init1(k);


    a.resize(s);
    b.resize(s);

    NTT(a,s,1);

    NTT(b,s,1);

    for(int i=0;i<s;i++)
    {
        a[i]=a[i]*b[i]%mod;

    }


    NTT(a,s,-1);

    int len=s-1;

    while(a[len]==0)
        len--;

    a.resize(len+1);


}

vector<ll>v[N];


int main ()
{

    init();

    int n,m,k;

    cin>>n>>m>>k;



    queue<int>q;

    for(int i=1;i<=m;i++)
    {

        int x;

        cin>>x;

        v[i].resize(x);


        for(int j=0;j<x;j++)
        {
            v[i][j]=C(x,j+1);

         


        }

       

        q.push(i);

    }


   while(q.size()>=2)
    {

        int q1=q.front();

        q.pop();

        int q2=q.front();

        q.pop();


        mul(v[q1],v[q2],v[q1].size()+v[q2].size());

        q.push(q1);


    }

cout<<v[q.front()][k-m];



    return 0;

}