雨羊的博客

分类
数学问题

容斥定理

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。简单来说，就是奇加偶减。举个例子：求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(

数学问题