0%

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$

Read more »

Native

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

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

Read more »

容斥求欧拉函数证明

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

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

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

Read more »

以前用 WordPress 搭过 blog,后来因为服务器过期和对 php 的不满作罢了。
加上最近几个月回归 OI、重新开始摸 code,感觉 blog 的意义又大了起来。
于是在作业没写完的一天下午,匆匆忙忙的搭好了 hexo。