STL

1.vector 动态数组，倍增的思想

vector<int> a(n, 3)初始化一个长度为nn的vectorvector,每个数字是33.

常用函数：

a.size(),a.empty(),a.clear()清空,a,front(),a.back(),a.push_back(),a.pop_back(),a.begin(),a.end(),

遍历方式：

vector<int> a;
for (int i = 0; i < 10; i++) a.push_back(i);
for (int i = 0; i < a.size(); i++) cout << a[i] << endl;
for (vector<int>::iterator i = a.begin(); i != a.end(); i++) cout << *i << endl;
for (auto x : a) cout << x << endl;

//支持比较运算
vector<int> a(3,4), b(4, 3);
if (a < b) puts("YES");

[Copy](javascript:;)

2.string 字符串

s.size(),s.empty(),s.clear().s.substr(),printf("%s\n",s.c_str()),s.length()

getline(cin, s);读入字符串可以读空格

cin.getline(a, 80);读入字符到字符数组aa，第二个参数是读入长度。

strcat(a, b).将字符数组b全部加入到字符数组a后面。

strlen(a)。获取字符数组aa的长度

stringstream 利用流输入输出字符串。

stringstream ss;
ss << a << '.' << b << '.' << c << '.' << d << ':' << port;
还原地址和原串比较
return ss.str() == s;
streamstring在调用str()时，会返回临时的string对象。而因为是临时的对象，所以它在整个表达式结束后将会被析构。

[Copy](javascript:;)

sscanf函数可以返回匹配和赋值的个数，例如网络连接一题：

sscanf(s.c_str(), "%lld.%lld.%lld.%lld:%lld", &a, &b, &c, &d, &port) != 5

[Copy](javascript:;)

c_str()返回一个指向正规cc字符串的指针常量，内容与原stringstring相同，主要是为了让cc的函数使用合法

3.queue

q.push(),q.front(),q.back(),q.pop(),q.size(),q.empty(),无clear(),q = queue<int> ()清空

4.priority_queue

q.push(),q.top(),q.pop(),q.empty(),q.size()

定义默认大根堆(堆顶最大)

定义：priority_queue<Type, Container, Functional> \text{Type}Type 就是数据类型，\text{Container}Container 就是容器类型（\text{Container}Container必须是用数组实现的容器，比如\text{vector,deque}vector,deque等等，但不能用 \text{list}list。\text{STL}STL里面默认用的是\text{vector}vector），\text{Functional}Functional 就是比较的方式。

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆。

一般是：

升序队列，小顶堆

priority_queue <int,vector\<int>,greater\<int> > q;

降序队列，大顶堆

priority_queue <int,vector\<int>,less\<int> >q;

\text{greater}greater和\text{less}less是\text{std}std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个\text{operator()}operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

常用题型：贪心，通常需要维护两个价值，一个通过\text{sort}sort排序，另一个通过堆来完成。

struct node
{
	int d, p;
	bool operator<(const node &x) const { return p > x.p; } 
	//大于就是小堆，小于是大堆
} a[N];
priority_queue<node> q;

[Copy](javascript:;)

线性时间求前1,3,5\dots n1**,3,5…n个数字的中位数**

创立两个堆，一个大根堆，一个小根堆。首先第一个数字直接输出，并且加入到大根堆，接下来每次读入两个数字，保证小的进入大根堆，大的进入小根堆，这个时候由于大根堆元素始终比小根堆多11个，所以大根堆的堆顶就是中位数，然后每次读入两个数字加入的时候还需要判断一下，大根堆堆顶和小根堆堆顶的大小关系，如果大根堆堆顶大于小根堆堆顶就进行交换。

q1.push(x);
for (int i = 2; i <= n; i += 2)
{
	cin >> x >> y;
	if (x > y)
		swap(x, y);
	q1.push(x);
	q2.push(y);
	if (q1.top() > q2.top())
	{
		int a = q1.top();
		q1.pop();
		int b = q2.top();
		q2.pop();
		q1.push(b);
		q2.push(a);
	}
	cout << q1.top() << "\n";
}

[Copy](javascript:;)

5.stack

st.push(),st.top(),st.pop(),st.empty(),st.size()

6.deque

q.size(),q.empty(),q.clear(),q.front(),q.back(),q.push_front(),q.pop_back(),q.push_back(),q.pop_front(),支持迭代器常数很大

7.set map multiset multimap 基于平衡二叉树(红黑树),动态维护有序序列

size(),empty(),clear(),begin()/end()

setset无重复,multisetmultiset可以有重复。

insert()插入,find(),count()个数,erase(),如果传入具体的值则删除所有x,否则传入迭代器，删除这个迭代器。时间复杂度均为\text{O(log(n))}O(log(n))

支持lower_bound(),upper_bound(),不存在返回end()end()

map/multimapmap**/multima**p

insert() 插入的数是一个pair,erase() 输入参数是pair或者迭代器,find(),像用数组一样使用时间复杂度均为\text{O(log(n))}O(log(n))

支持lower_bound(),upper_bound(),不存在返回end()end()

8.unordered_set unordered_map unordered_multiset unordered_multimap 哈希表

和上面类似，绝对大部分操作时间复杂度\text{O(1)}O(1)

不支持lower_bound(),upper_bound()

9.bitset 压位

bitset<10000> s;
//支持位运算,==,!=,[]
count();//多少个1
any()//是否至少有一个1
none()//是否全为空
set()//所有位置为1
set(k,v)//第k位为v
reset()//所有位为0
flip(),flip(k)//取反

//bitset优化埃式筛
bitset<N> vis;
void Prime(int n)
{
	vis.set();
	vis[0] = vis[1] = 0;
	for (int i = 2; i * i <= n; i++)
	{
		if (vis[i])
		{
			for (int j = i << 1; j <= n; j += i)
				vis[j] = 0;
		}
	}
}

[Copy](javascript:;)

数学专题

数论

1. 位运算(&,|,^,>>,<<,~)

①异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即

aa \bigoplus⨁ bb \bigoplus⨁ bb=aa。

②取反：二进制补码按位取反，有符号位也会取反。右移就是除以2，左移就是乘2.

③位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符

④位运算的应用,位运算一般有三种作用：

(1) 高效地进行某些运算，代替其它低效的方式。

(2) 表示集合。（常用于状压 DP)

(3) 题目本来就要求进行位运算。

判断一个数是不是2的非负整数次幂：

n & (n - 1)== 0;

[Copy](javascript:;)

对2的非负整数次幂取模：

x & (mod - 1);

[Copy](javascript:;)

获取 a 的第 b 位，最低位编号为 0

int getBit(int a, int b) { return (a >> b) & 1; }

[Copy](javascript:;)

将 a 的第 b 位设置为 0 ，最低位编号为 0

int unsetBit(int a, int b) { return a & ~(1 << b); }

[Copy](javascript:;)

2. 快速幂

加速快速幂：根据费马小定理，如果p是一个质数，而整数a不是p的倍数，则有

a^{（p-1）}≡1（mod p）a（p−1）≡1**（modp**）。

3. 扩展欧几里得定理

1. gcd(a,b)=gcd(b,agcd(a,b)=gcd**(b,**a%b)b)
2. 用于解ax+by=cax**+by**=c不定方程的解(a,x,b,y都是整数a,x,b,y都是整数)，根据裴蜀定理，ax+by=cax**+by**=c有解的充分必要条件是cc%gcd(a,b)0gcd(a,b)**0,给出证明，设gcd(a,b)==dgcd**(a,b)==d,则a=nd,b=mda=nd**,b=md**。则ndx+mdy=cndx+mdy=c，化简得d(nx+my)=cd(nx**+my**)=c，则cc一定是dd的倍数，证毕。
3. 实际是先ax+py=gcd(a,b)a∗x+p∗y=gcd(a,b)这个方程后，反推出原方程的解，给解出来的xc/gcd(a,b)x∗c/gcd(a,b)就是ax+by=cax**+by**=c的一个解，那么我们解这个方程首先根据裴蜀定理进行化简，令a=b,b=aa=b,b=a%bb，则该式子是bx+abx**+a%by=gcd(b,aby=gcd(b,a%b)b),由于gcd(b,agcd**(b,a%b)b)=gcd(a,b)=gcd**(a,b),得 bx+abx+a%by=gcd(a,b)by=gcd(a,b)**, 即ay-b(x-a/by)=gcd(a,b)ay−b**(x−a/b∗y)=gcd**(a,b),递归求解到最后，b==0的时候，得到一组解，x=1,y=0x=1,y=0.也就是a1+b0=gcd(a,0)a∗1+b∗0=gcd(a,0),gcd(a,0)gcd(a,0)当然就是aa了.

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return d;
}

[Copy](javascript:;)

4. 此时得到的xx只是ax+by=gcd(a,b)ax**+by**=gcd(a,b)的一组特解，ax+kab-kab+by=cax**+kab−kab+by**=c,则a(x+kb)+b(y-ka)=ca(x+kb)+b(y−ka**)=c.我们将要求出来的 x,yx**,y 仅仅保证满足 ax + by = 1ax**+by**=1而 xx 不一定是最小正整数解。有可能太大，也有可能是负数
5. 根据特解，x=x*c/gcd(a,b)x=x∗c/gcd(a,b)就得到原方程的一组解。所以如果xx太小，我们就加bb刚好大于等于00，反之减bb。
6. 最小非负整数解：(x**(x%(b/d)+b/d)(b/d)+b/d)%(b/d)(b/d),需注意若a<0a**<0，需改变符号。
7. 显然最小时 d_x=\frac{b}{\gcd(a,b)}dx​=gcd(a,b)b​， d_y=\frac{a}{\gcd(a,b)}dy​=gcd(a,b)a​，在d=\frac{1}{\gcd(a,b)}d=gcd(a,b)1​时取到

那么通解形式就出来了，

x=x_1+sd_x xx=x1​+sdx​x y=y_1-sd_yy=y1​−sdy​ 其中，ss 是任意整数

而且，随着 xx 增大 yy减小 （废话，它们的和一定）

而且，ss 越大，xx 越大，yy越小，反之亦然（重点）

4. 质因数分解

for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			int cnt = 0;
			while (n % i == 0)
			{
				n /= i;
				cnt++;
			}
			v.push_back((node){i, cnt});
		}
	}
	if (n != 1)
	{
		v.push_back((node){n, 1});
	}

[Copy](javascript:;)

1. 要使得s_i^k \mid m_1^{m_2}sik​∣m1m2​​,则si分解的质因数必须包含m1的所有质因子。

5.线性复杂度解决1~n mod p的逆元(pp为质数)

过程：

1. 令p=ki+rp=ki+r,kk为p/ip/i的商，rr为余数。则k=⌊p/i⌋k=⌊p/i⌋（向下取整）, r=p \ mod\ ir=p mod i.(i<p,k<p,r<ii<p,k<p,r<i)
2. 两边同时乘以i^{-1}r^{-1}i−1∗r−1,得到kr^{-1}+i^{-1}\equiv\ 0 (mod\ p)k∗r−1+i−1≡** 0(mod p)**
3. 移项得i^{-1}\equiv -k*r^{-1}(mod\ p)i−1≡−k∗r−1**(mod p)**
4. 带入刚才得kk和rr的表达式,得到i^{-1}\equiv -⌊p/i⌋*(p \ mod\ i)^{-1}(mod\ p)i−1≡−⌊p/i⌋∗(p mod i)−1**(mod p)**
5. 由于p \ mod\ i<ip mod i<i,所以在求出i^{-1}i−1之前已经求出(p \ mod\ i)^{-1}(p mod** i)−1**
6. 用数组inv[i]记录i^{-1}i−1,则inv[i]=-p/i*inv[p \ mod\ i]\ mod \ p−p**/i∗inv**[p mod i]** mod **p
7. 同时要注意，为了保证i^{-1}>0i−1>0，上式需要两边加上p。
8. 则inv[i]={p-p/i*inv[p \ mod\ i]\ mod \ p}p−p/i∗inv**[p mod i]** mod p
9. 然后可以轻松的由inv[1]=1inv**[1]**=1,在O(1)的时间推出其余答案。
10. 正常可以利用exgcd和快速幂结合费马小定理在log时间解决

6.中国剩余定理

常用来解一元线性同余方程组

一般从这个问题引入，某物品三三数之余二，五五数之余三，七七数之余二。问物几何？

写成方程组的形式就是求解

\left{ \begin{matrix} x\equiv\ 2\ mod\ 3 \ x\equiv\ 3\ mod\ 5 \ x\equiv\ 2\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 2 mod 3x≡ 3 mod 5x≡ 2 mod 7​

首先，若x_0x0​为原方程的一个解，那么x_0+357*k，k\in 整数x0​+3∗5∗7∗k，k∈整数，也是一个解

解上述方程组其实首先需要解以下3个方程，这里有点线性代数的意思。

\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7​

\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 1\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 0 mod 3x≡ 1 mod 5x≡ 0 mod 7​

\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 1\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 0 mod 3x≡ 0 mod 5x≡ 1 mod 7​

记上述三组的解记为

\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡​100​⎦⎤​

\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡​010​⎦⎤​

\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡​001​⎦⎤​

则原方程的解为 22∗\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡​100​⎦⎤​*+33∗\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡​010​⎦⎤​*+22∗\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡​001​⎦⎤​*

问题的关键显然是求上述三组解。 上述三组解是这样求的，先来看第一个。

\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧​x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7​

x一定是35的倍数x一定是35的倍数，所以设x=35*yx=35∗y,那么35y\ \equiv\ 1\ mod\ 335y** ≡ 1 mod 3,这里容易求出yy是22**,实际也能看出就是逆元。

求出22以后，x=35*2=70x=35∗2=70，那么第一个方程组的一个特解就出来了。

同理求出其余的两个方程组的特解分别是x=21,x=15x=21,x=15。

则原方程的解为270+321+2*15\ \equiv\ 23\ mod\ 1052∗70+3∗21+2∗15 ≡ 23 mod 105 ，所以这里就求出了23.

因此从这里也能看出线性同余方程组的求解方式，方法就是。

\left{ \begin{matrix} x\equiv\ b_1\ mod\ a_1 \ x\equiv\ b_2\ mod\ a_2 \ …… \ x\equiv\ b_k\ mod\ a_k \ \end{matrix} \right.⎩⎨⎧​x≡ b1​ mod a1​x≡ b2​ mod a2​……x≡** bk​ mod ak​​**

首先还是按照刚才的方式分出多个方程组来，求出每一个的，最后求和。

1. 首先求出N=a_1a_2……a_kN=a1​∗a2​∗*……∗ak​**
2. 对于每一组方程我们按照上面的例题思路来求解，设m=N/a_im=N/ai​,那么紧接着我们需要求出mx\ \equiv\ 1\ mod\ a_imx** ≡ 1 mod ai​,求出这个x以后x**以后。
3. 那么最终这个方程组的解就是mxb_im∗x∗bi​，回想刚才不就是35是m，x求逆元是2，b_i是235是m，x求逆元是2，bi​是2，所以是352235∗2∗2,对应上面的2*702∗70.
4. 然后循环求和，并且求和的时候对NN取余得到答案。

7.扩展中国剩余定理

求解同余方程组

\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\ x\equiv\ a_3(\mod m_3) \quad\ ...\quad\x\equiv\ a_k(\mod m_k) \quad\end{aligned}\right.⎩⎨⎧​x≡ a1​(modm1​**)x≡** a2​(modm2​**)x≡** a3​(modm3​**)...x≡ ak​(modmk​**)​​其中m_1,m_2,m_3...m_km1​,m2​,m3​...mk​

为不一定两两互质的整数， 求xx的最小非负整数解.

类似于求多个数字gcdgcd 的方法，先求出前两个的解，然后不停的合并，前两个方程组可以利用扩欧求出最小解，然后循环下去即可。

ll tmp1 = b[1], tmp2 = a[1], ans;
for (int i = 2; i <= n; i++)
{
    ll A, B, C, X, Y;
    C = b[i] - tmp1;
    A = tmp2, B = a[i];
    if (C < 0)
    {
        swap(b[i], tmp1);
        swap(A, B);
    }
    ll g = gcd(A, B);
    C = b[i] - tmp1;
    exgcd(A, B, X, Y);
    X *= C / g, Y *= C / g;
    Y %= A / g;
    if (Y > 0)
    {
        Y -= A / g;
    }
    ans = (b[i] - B * Y) % lcm(a[i], tmp2);
    tmp1 = (b[i] - B * Y) % lcm(a[i], tmp2);
    tmp2 = lcm(a[i], tmp2);
}

[Copy](javascript:;)

8.Lucas定理

定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解（详见 排列组合），但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 LucasLucas 定理。

公式：C(n,m)\ mod\ p=C(n/p,m/p)C(n%p,m%p)\ mod\ pC(n,m)* mod p=C(n/p,m/p)∗C**(n%p,m%p)** mod **p

递归操作下去，当 m0m0,返回11.也就是C(n,0)1C(n,0)****1

Lucas(n,m)\ mod\ p=Lucas(n/p,m/p)C(n%p,m%p)\ mod\ pLucas*(n,m)** mod p=Lucas**(n/p,m/p)∗C**(n%p,m%p)** mod **p

ll Lucas(ll n, ll m, ll p)
{
    if(m == 0)return 1;
    return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

[Copy](javascript:;)

求解C(n%p,m%p)\ mod\ pC(n%p,m%p)** mod **p的时候

当n,mn,m不大的时候，可以预处理出所有的阶乘答案存到数组。数字大的时候可以单独去算。

C(n,m)=n!/(n-m)!m!C(n,m)=n!/(n−m*)!∗m**!也就是(n*(n-1)……(n-m+1))/m!\ mod\ p**(n∗**(n−1)∗……∗(n−m+1))/m! mod p 分子分母都可以直接计算，牵扯到除法因此需要求m!*x\equiv\ 1\ mod\ pm!∗x≡ 1 mod p求出这个xx,也就是逆元，由于pp是质数，因此用费马小定理求解即可。

ll quick_pow(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a, ll p) //求a mod p下的逆元。
{
    return quick_pow(a, p - 2, p);
}
ll C(ll n, ll m, ll p)
{
    if (m > n)
        return 0;
    ll up = 1, down = 1;
    for (int i = n - m + 1; i <= n; i++)
        up = up * i % p;
    for (int i = 1; i <= m; i++)
        down = down * i % p;
    return up * inv(down, p) % p;
}

[Copy](javascript:;)

9.整数唯一分解定理

根据任意一个正整数的唯一分解定理。任何一个数字aa都可以写成。aa = p_1^{k_1}p_2^{k_2}……p_n^{k_n}p1k1​​∗p2k2​​∗**……∗pn​∗kn​**，这里的p_ipi​就是分解的质因数，例如2424 = 2^3*3^123∗31。

约数和公式，对于已分解的aa = p_1^{k_1}p_2^{k_2}……p_n^{k_n}p1k1​​∗p2k2​​∗**……∗pn​∗kn​**，所有的因子之和就是sumsum = (1+p_1+p_1^2+p_1^3+……+p_1^{k_1})(1+p_2+p_2^2+p_2^3+……+p_2^{k_2})……*(1+p_n+p_n^2+p_n^3+……+p_n^{k_n})(1+p1​**+p12​**+p13​**+……+p1k1​​**)∗(1+p2​+p22​**+p23​**+……+p2k2​​**)∗……∗(1+pn​+pn2​**+pn3​**+……+pnkn​​**).

10.快速乘

由于计算机底层设计的原因，做加法往往比乘法快的多，因此将乘法转换为加法计算将会大大提高（大数，比较小的数也没必要）乘法运算的速度，除此之外，当我们计算ab%moda∗b%mod的时候，往往较大的数计算aba∗b会超出long longlonglong的范围，这个时候使用快速乘法方法也能解决上述问题．

快速乘法的原理就是利用乘法分配率来将aba∗b转化为多个式子相加的形式求解（注意这时使用乘法分配率的时候后面的一个乘数转化为二进制的形式计算）．举个栗子 　　2014　＝　20*(1110)2 = 20*(2^3)1 + 20(2^2)1+20(2^1)1+20(2^0)0 = 160+80+40=280.20∗14　＝　20∗*(1110)2=20∗**(23**)∗1**+20∗**(22**)∗1**+20∗**(21**)∗1**+20∗**(20**)∗0**=160+80+40=**280.

ll qmul(ll a, ll b, ll mod)
{
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

[Copy](javascript:;)

利用龟速乘解决快速幂爆long long

long long quick_mul(long long x, long long y, long long mod)
{
    long long ans = 0;
    while (y)
    {
        if (y & 1)
		{
			ans += x;
			ans %= mod;
		}
        x = x + x;
		x %= mod;
        y >>= 1;
    }
    return ans;
}

long long quick_pow(long long x, long long y, long long mod)
{
    long long sum = 1;
    while (y)
    {
        if (y & 1)
        {
			sum = quick_mul(sum, x, mod);//原本相乘转换为龟速乘加法
			sum %= mod;
		}
        x = quick_mul(x, x, mod);
		//原本相乘转换为龟速乘加法
		x %= mod;
        y = y >> 1;
    }
    return sum;
}

[Copy](javascript:;)

11.欧拉筛

主要是优化掉了埃式筛中的重复筛

for (int i = 2; i <= N; i++)
	{
		if (!vis[i])
			prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
		{
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}

[Copy](javascript:;)

12.欧拉函数

欧拉函数，即ϕ(n)ϕ(n)，表示的是小于等于n和n互质的数的个数,如果n是质数，ϕ(n) = n - 1ϕ(n)=n−1

如果gcd(a,b)=1gcd(a,b)=1,则ϕ(a*b) = ϕ(a)*ϕ(b)ϕ(a∗b)=ϕ(a)∗ϕ(b)

n是奇数,ϕ(2n)ϕ(2n**)** = ϕ(n)ϕ(n)

ϕ(C)=C∗∏(1−p/1)ϕ(C)=C∗∏**(1−p/1**)

令T=p_1^{c_1-1}p_2^{c_2-1}……p_m^{c_m-1}T=p1c1​−1​∗p2c2​−1​……∗pmcm​−1​,F=p_1p_2……p_mF=p1​∗p2​∗*……∗pm​**

ϕ(C)=T∗F*∏(1−p/1)ϕ(C)=T∗F∗∏**(1−p/1**),ϕ(C)=T∗∏(p_i-1)ϕ(C)=T∗∏**(pi​−1)**

对于c_2=c_1*pc2​=c1​∗p

若c_2%c_10c2​%c1​0,ϕ(c_2)=ϕ(c_1)pϕ(c2​)=ϕ(c1​*)∗p**,否则ϕ(c_2)=ϕ(c_1)*(p-1)ϕ(c2​)=ϕ(c1​**)∗(p−1)**

int euler_phi(int n)
{
    double ans = 1;
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ans = ans * (1 - 1.0 / i);
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        ans = ans * (1 - 1.0 / n);
    return ans * res;
}

[Copy](javascript:;)

若gcd(a,m) = 1gcd(a,m)=1,则a^{ϕ(m)}\equiv\ 1(mod\ m)aϕ(m)≡ 1(mod** m)**

多个数字的欧拉函数利用线性筛求

int n, p[N], phi[N], cnt;
bool vis[N];
void prime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = 1;
            if (i % p[j])
            {
                phi[i * p[j]] = phi[i] * (p[j] - 1);
            }
            else
            {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
        }
    }
}

[Copy](javascript:;)

∀n>1∀n**>1,1\sim n1∼n中与nn互质的数的和为n∗ϕ(n)/2n∗ϕ**(n)/2.

扩展欧拉定理∀a,n,a^{2ϕ(n)}\equiv\ a^{ϕ(n)}\ (mod\ n)∀a**,n,a2ϕ(n)≡ aϕ**(n)** (mod** n)

若b>ϕ(n)b>ϕ(n),则a^b\equiv\ a^{b%ϕ(n)+ϕ(n)}\ (mod\ n)ab≡ ab**%ϕ(n)+ϕ(n) (mod** n)

13.容斥原理

解决集合问题，一个的减去两两的加上三三的……

14.线性代数

1. 矩阵乘法and矩阵快速幂

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int N = 105;
ll n, k;
struct martix
{
	ll a[N][N];
	martix() { memset(a, 0, sizeof(a)); }
	inline void build()
	{
		for (int i = 1; i <= n; i++)
			a[i][i] = 1;
	}
} a;
inline martix operator*(const martix &x, const martix &y)
重载运算符
{
	martix z;
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
			}
		}
	}
	return z;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> a.a[i][j];
		}
	}
	martix ans;
	ans.build();
	while (k)
	{
		if (k & 1)
		{
			ans = ans * a;
		}
		a = a * a;
		k >>= 1;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << ans.a[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

[Copy](javascript:;)

注意矩阵乘法不满足交换律

2. 求解某一数列

例如斐波那契数列等，主要是找到关系矩阵，利用矩阵乘法和快速幂进行求解 矩阵求斐波那契数列第n项代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
ll n;
struct martix
{
    ll a[3][3];
    martix() { memset(a, 0, sizeof(a)); }

} a, ans;
inline martix operator*(const martix &x, const martix &y)
{
    martix z;
    for (int k = 1; k <= 2; k++)
    {
        for (int i = 1; i <= 2; i++)
        {
            for (int j = 1; j <= 2; j++)
            {
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            }
        }
    }
    return z;
}
int main()
{
    cin >> n;
    if (n <= 2)
    {
        cout << 1;
        return 0;
    }
    a.a[1][1] = 1;
    a.a[1][2] = 1;
    a.a[2][1] = 1;
    a.a[2][2] = 0;
    ans.a[1][1] = ans.a[1][2] = 1;
    n = n - 2;
    while (n)
    {
        if (n & 1)
        {
            ans = ans * a;
        }
        a = a * a;
        n >>= 1;
    }
    cout << (ans.a[1][1]) % mod;
}

[Copy](javascript:;)

15. 常用的数学推导

a +2a^2+3a^3+……+na^n=(na^{n+1}-(a^{n+1}-a)/(a-1))/(a-1)a+2a2+3a3+……+nan=(nan**+1−**(an**+1−a)/(a−1))/(a−1)**

所以任何的f(i)a_i^{i}f(i)aii​均可以计算出来

1+4+……+n^2=n(n+1)(2n+1)/61+4+……+n2**=n(n+1)(2n+1)**/6

1+8+……+n^3=(n(n+1)/2)^21+8+……+n3**=(n(n+1)/2**)2

分数裂项：1/(i+1)i=1/i-1/(i+1)1/(i+1)i=1/i−1/(i+1)

123+234+……+n*(n+1)*(n+2)1∗2∗3+2∗3∗4+……+n∗**(n+1)∗(n+2)**

i*(i+1)(i+2)=i(i+1)(i+2)((i+3)-(i-1))/4=(i*(i+1)(i+2)(i+3)-(i-1)i(i+1)*(i+2))/4i∗**(i+1)∗(i+2)=i∗(i+1)∗(i+2)∗((i+3)−(i−1))/4=(i∗(i+1)∗(i+2)∗(i+3)−(i−1)∗i∗(i+1)∗(i+2))**/4

原式=n*(n+1)(n+2)(n+3)/4n∗**(n+1)∗(n+2)∗(n+3)**/4

枚举方式：

1. 枚举结果可能出现的次数。洛谷P6042
2. 枚举结果中拆式子

常用的换元方式：

1. gcd(a,b)=d,a=a1d,b=b1d,lcm(a,b)=a1b1dgcd(a,b)=d,a=a1∗d,b=b1∗d**,lcm(a,b)=a1∗b1∗d**
2. 设y=a&b,x=a-z,z=b-y，那么a|b=x+y+z,a^b=x+zy=a&b,x=a−z,z=b−y，那么a∣b=x+y+z,ab**=x+**z,这个可以画图很好的理解。

微扰法证明贪心：

一般是通过交换相邻两项观察带来的变化来解决问题。