容斥定理

要计算几个集合并集的大小,我们要先将所有单个集合的大小计算出来,然后减去所有两个集合相交的部分,再加回所有三个集合相交的部分,再减去所有四个集合相交的部分,依此类推,一直计算到所有集合相交的部分。 简单来说,就是奇加偶减。 举个例子: 求1~n中多少个数不是2,3,5,7的倍数,当n=10,结果只有

分解质因子

任何一个合数可以分解为几个质数的乘积,这些质数也必然是这个合数的约数。 超时模板: #include<bits/stdc++.h> using namespace std; vector<int> fun(int n) { vector<int> v; for (int i = 2; i <=

素数

素数判断 bool is_prime(int u) { if (u == 0 || u == 1)return false; if (u == 2)return true; if (u % 2 == 0)return false; for (int i = 3; i <= sqrt(u);

欧拉降幂

欧拉定理: phi(n)为n的欧拉函数值,当n为质数时,n的欧拉函数值为n-1 降幂公式: 对于一个问题求 a^b %n 可以直接根据右边的条件把式子转换成上面三个中的一个

欧拉函数

参考链接 浅谈欧拉函数 什么是欧拉函数 欧拉函数是小于x的整数中与x互质的数的个数,一般用φ(x)表示。特殊的,φ(1)=1。 如何计算欧数值拉函 欧拉函数的通式:φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn),其中p1, p2……pn为n的所有

组合数C(n,m)的计算

C(n,m)的计算方式: 1.公式:C(n,m) = n!/((n-m)! * m!),在算法上较难实现,阶乘很快会爆 long long 2.递推:C(n,m) = C(n-1,m-1) + C(n-1,m) 在算法上当然会采用第二种方式计算,而且因为 C(n,m)本身值很大,所以大多数碰见它的情

a^b%c

利用二进制来写,提供一种新思路,也更加简洁,迅速 //res=ab%c //将b转化为二进制,1即为有这一个数,0即没有 //例如9的二进制1001 即 23+20 //则a9=a8*a1; a23和a20 的乘积 //求a的b次方对c取模 //(ab)%c==(a%c)(a%b) int fun(