模板

模板

素数：：

const int N = 10000010;
int prime[N],pe=0;
bool isprime[N];
void getprime(int n)
{memset(isprime,1,sizeof(isprime));isprime[1] = 0;int i,j;for(i=2;i<=n;i++){if(isprime[i])prime[pe++] = i;for(j=0;j<pe && i*prime[j]<=n;j++){isprime[i*prime[j]] = 0;if(i%prime[j] == 0)break;}}
}

逆元：：

    ---单一逆元写法

    a/b = a*pow(b,MOD-2);

    pow(a,b) 为 a^b 的快速幂；     MOD为大素数，如1e9+7

    ---递推打表写法

typedef long long ll;
const int N=100100;
const int MOD = 1e9+7;
ll inv[N];    //逆元
void count_inv()
{inv[1] = 1;int i;for(i=2;i<N;i++)inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;
}

欧拉函数：：

    定义，φ(n) 为1~n 中与 n 互质的数的个数

typedef long long ll;
const int N=100100;
const int MOD = 1e9+7;
ll res[N];	//欧拉函数
void count_ol()
{memset(res,0,sizeof(res));res[1] = 1;int i,j;for(i=2;i<N;i++){if(!res[i]){for(j=i;j<N;j+=i){if(!res[j])res[j] = j;res[j] = res[j]/i*(i-1);}}}
}

莫比乌斯函数：：

    定义：

typedef long long ll;
const int N=100100;
const int MOD = 1e9+7;
ll mu[N];	//莫比乌斯函数 
void init_1()
{mu[1] = 1;for(i=1;i<N;i++)for(j=2*i;j<N;j+=i)mu[j] -= mu[i];
}

质因数分解：：

//对 n 分解质因数 
int n,i;
vector<int> pn;
for(i=2; i*i<=n; i++)
{if(n%i == 0){pn.push_back(i);while(n%i == 0)n /= i;}
}
if(n > 1)pn.push_back(n);