东灯的寒舍

GCD

求Gcd

两种常用方法，均基于辗转相除，第二种方法在某些问题的处理上可能出锅。

1
2
3
4
5
6
7

inline int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
inline int _gcd(int x,int y){
    while(y^=x^=y^=x%=y);
	return x;
}

求LCM

$gcd(a,b)lcm(a,b)=ab$

Native

任意一个大于$1$的正整数都能被唯一分解成有限个质数的乘积，可写作：

其中 $c_i$ 都是正整数，$p_i$ 均为质数，且满足 $p_1<p_2<…<p_m$。

容斥求欧拉函数证明

以前一直对容斥原理求欧拉函数的求法有些不解，昨晚领悟透彻之后准备记录一下。

首先对于一个正整数 $n$，在 $1-n$ 中与其互质的数满足一个条件：他们没有相同的质因子

因此考虑从 $n$ 中删除这些相同质因子的贡献，针对每个质因子 $p$，在 $1-n$ 中都存在：

首先%%%zzz

人生中没做过几道数论题，经过 zzz 的悉心指导大概算是会了这道…题

题目要求为求