原根与NTT 五千字详解

欧拉定理

若 m,a互质 则  

阶的概念

若a,m互质，使得的最小正整数n称为a模m意义下的阶，记作

原根的概念

若,即a的阶等于m的欧拉函数，则称a为原根

阶的性质

        在模m意义下两两不同，之后开始进入周期

阶周期性

   即在模阶意义下相同的两个指数，对应mod m下的幂数也相同

 即阶是欧拉函数的因子

原根存在定理

只有模 2,4,才存在原根，其中p是奇数，是质数，也就是奇质数

原根的判定定理

设m>1,g为正整数，且g,m互质，g是m的原根当且仅当，的全部质因子qi

都满足

最小原根求解全部原根

在找出最小原根p的情况下， p^k只需要满足 

求解原根模板

第一步 欧拉筛 预处理出范围内所有质数 ，以及欧拉函数，原根存在性

依据为 原根存在定理

 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;

        }
    }

第二步，读入判断数字，首先判断是否具有原根，有的话，对其欧拉函数进行质因数分解，作为原根判断合理性的依据

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 ;

}

第三步，枚举最小原根，最小原根值一般很小，可以直接枚举。根据原根定义，其阶数为phi[p],判断依据是其 phi[p]次幂应该mod m =1。然后不能仅仅满足这一个条件就能判断phi[p]就是其阶数，还需要原根判定定理，枚举欧拉函数质因数分解后的因子，x的欧拉函数除以因子次幂在mod m情况下不能等于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;

}

第四步，寻找到最小原根，枚举最小原根的k次幂，满足 gcd(k,phi[p])=1才行

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 ;

}

【模板】原根 - 洛谷

# 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模板

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]]);
	}//前面和FFT一样
	for (int mid=1;mid<len;mid*=2)
	{
		int tmp=pow(g,(mod-1)/(mid*2));//原根代替单位根
		if (inv==-1)tmp=pow(tmp,mod-2);//逆变换则乘上逆元
		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;//注意取模
			}
		}//大体和FFT差不多
	}
}

挑选队友

 生成函数很好设置，唯一细节在于vector容器下标的设置，这里采用0代表1,在运算的过程中，误差也就产生了下标偏移

比如 v1[0]代表1，v1[1]代表2

v2[0]代表1，v2[1]代表2

进行一次运算

v1[0]=v1[0]*v2[0] 也就是说，v1[0]代表了2

v1[1]代表了3

进行m次运算

v[pos]代表 pos+1+m-1 =pos+m

所以最终答案要输出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;

}