杜教筛 与 数论函数（狄雷克卷积）

   为了改变数论只会GCD的尴尬局面，我们来开一波数论：

     数论函数：

• 数论函数是定义域在正整数的函数。
• 积性函数： ) 。
• 常见积性函数： ) （因子和）。
• 单位函数 ： ] 。
• 常见完全积性函数： ) 。

     我们 有以下令人窒息的操作：

        (F*G)（x）=∑d|n F（d）*G（n/d）

    这种操作我们称之为狄雷克卷积。满足交换律，结合律，分配律以及 f 。

    我们有:      )

)

1

    都可以由积性函数的性质再套一个乘法分配率可以证出来。

    我们有两个重要的数论函数 ) 。

     )，1到n里面与N互质的数的个数。有重要的等式：φ*1=id

     μ的逆元。 我们发现狄雷克卷积可以构成一个群，生成元是e ，1* μ=e，我们又知道*1又叫求该函数的狄雷克前缀和，那么再卷上μ就是原来的函数了。 

     我们设F=f*1，则 f=F* μ 

      那么我们就可以做一些简单的题目了：

      bzoj 3884 .这道题我们要一个结论：

      X^i=X^（i>φ（p）?i mod  φ（p）+φ（p）：i） （mod p）

 　 特殊的 ，我们有 X^i=X^(i%(p-1)) (mod p) p为质数。

     我们还要知道φ（φ（p））<n/2,那么我们不妨迭代指数，最多迭代log p次指数为1，我们停止迭代。

    

#include<bits/stdc++.h>
using namespace std;
int sed(int &p){
    int ll=0;
    while (p%2==0) ll++,p>>=1; return ll;
}
int fai(int x){
     int i,re=x;  
    for(i=2;i*i<=x;i++)  
        if(x%i==0)  
        {  
            re/=i;re*=i-1;  
            while(x%i==0)  
                x/=i;  
        }  
    if(x^1) re/=x,re*=x-1;  
    return re;  
}
long long QP(long long x,int y,int p){
      long long re=1;  
    while(y)  
    {  
        if(y&1) (re*=x)%=p;  
        (x*=x)%=p; y>>=1;  
    }  
    return re; 
}
long long dos(int p){
    if (p==1) return 1;
    int k=sed(p), fi=fai(p);
    long long re=dos(fi);
    (re+=fi-k%fi)%=fi;  
  re=QP(2,re,p)%p;  
  return (re<<k);  
}
int main () {
    int t,p;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&p); 
        printf("%lld\n",dos(p)%p);
    }
}

View Code