1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdlib>  5 #include<cmath>  6 #include<map>  7 #include<iostream>  8 using namespace std;  9 typedef long long ll; 10 #define pi  acos(-1.0) 11 const int mod=1e9+7; 12  13  14 const int maxn=1000007; 15 bool is_prime[maxn]; 16 int prime[maxn]; 17 void AIsieve(int n){ 18     int cnt=0; 19     memset(is_prime,1,sizeof(is_prime)); 20     is_prime[0]=is_prime[1]=0; 21     for(int i=2;i<n;i++){ 22         if(is_prime[i]){ 23             prime[cnt++]=i;//保存素数 24             for(int j=i*i;j<n;j+=i)//i*i开始进行了稍微的优化 25                 prime[j]=0;//不是素数 26         } 27     } 28     return ; 29 } 30  31  32 const int MAXN=3000001; 33 int prime[MAXN];//保存素数 34 bool vis[MAXN];//初始化 35 int LSsieve(int n){ 36     int cnt=0; 37     memset(vis,0,sizeof vis); 38     for(int i=2;i<n;i++){ 39         if(!vis[i]) prime[cnt++]=i; 40         for(int j=0;j<cnt&&i*prime[j]<n;j++){ 41             vis[i*prime[j]]=1; 42             if(i%prime[j]==0)   break; 43         } 44     } 45     return cnt;//返回小于n的素数的个数  46 } 47  48  49 int phi[maxn]; 50 void phisieve(int n){ 51     for(int i=1;i<n;i++)  phi[i]=i; 52     for(int i=2;i<n;i++) 53         if(i==phi[i]) //此时i为素数 54             for(int j=i;j<n;j+=i)  //j累加i 55                 phi[j]=phi[j]/i*(i-1); //j有因子i,而且i是素数,正是欧拉函数 56 } 57  58  59  60 //将求素数和欧拉函数值都线性解出 61 int prime[MAXN];//保存素数 62 bool vis[MAXN];//初始化 63 int phi[MAXN];//欧拉函数 64 void Lphisieve(int n){ 65     int cnt=0; 66     for(int i=2;i<n;i++){ 67         if(!vis[i]){ 68             prime[cnt++]=i; 69             phi[i]=i-1;// if p is prime,then phi[i]=i-1 70         } 71         for(int j=0;j<cnt&&i*prime[j]<n;j++){ 72             int k=i*prime[j]; 73             vis[k]=true; 74             if(i%prime[j]==0){ 75                 phi[k]=phi[i]*prime[j]; 76                 break; 77             } 78             else   phi[k]=phi[i]*(prime[j]-1); 79         } 80     } 81 } 82  83 //莫比乌斯函数一般筛法 84 int mu[1000020]; 85 void sievemu(int n){ 86     mu[1]=1; 87     for(int i=1;i<=n;i++){ 88         for(int j=i+i;j<=n;j+=i){ 89             mu[j]-=mu[i]; 90         } 91     } 92 } 93  94  95 //莫比乌斯函数线性筛法 96 const int maxn=60000+5; 97 bool vis[maxn]; 98 int prime[maxn],mu[maxn]; 99 void init_mu(int n){100     int cnt=0;101     mu[1]=1;102     for(int i=2;i<n;i++){103         if(!vis[i]){104             prime[cnt++]=i;105             mu[i]=-1;106         }107         for(int j=0;j<cnt&&i*prime[j]<n;j++){108             vis[i*prime[j]]=1;109             if(i%prime[j]==0)   {mu[i*prime[j]]=0;break;}110             else { mu[i*prime[j]]=-mu[i];}111         }112     }113 }114 115 ll mod_pow(ll x,ll n,ll p){116     ll res=1;117     while(n>0){118         if(n&1)    res=res*x%p;119         x=x*x%p;120         n>>=1;121     }122     return res;123 }124 125 map<ll,int>mp;126 ll bsgs(ll a,ll b,ll c){127     mp.clear();//清空map128     ll tmp,m=ceil(sqrt(c));129     //等于0的情况130     tmp=b%c;131     mp[tmp]=0;132     for(int j=1;j<=m;j++){133         tmp=tmp*a%c;134         mp[tmp]=j;135     }136     tmp=1;137     ll t=mod_pow(a,m,c);138     for(int i=1;i<=m;i++){139         tmp=tmp*t%c;140         if(mp[tmp]) return i*m-mp[tmp];141     }142     return -1;143 }144 //sqrt(n)求欧拉函数值145 ll euler_phi(int n){146     int res=n;147     for(int i=2;i*i<=n;i++){148         if(n%i==0){149             res=res/i*(i-1);150             while(n%i==0) n/=i;151         }152     }153     if(n!=1) res=res/n*(n-1);154     return res;155 }156 157 ll inv(int x,int mod){158     return mod_pow(x,mod-2,mod);159 }160 161 ll extgcd(ll a,ll b,ll &x,ll &y){162     ll d=a;163     if(b)   d=extgcd(b,a%b,y,x),y-=a/b*x;164     else  x=1,y=0;165     //return (x+b)%b;166     return d;167 };