欧几里得算法\forall a,b\in \N,\gcd(a,b)=\gcd(b,a\bmod b)证明:
考虑记a与b的公因数为d\\\because \exist t,k,r\in\N,b=t\cdot d,a=k\cdot (t \cdot d)+r\\\because d\mid b,d\mid a\\\therefore \exist x\in\N,x\cdot d=a=k⋅(t⋅d)+r\\\quad \Leftrightarrow x=\dfrac{k⋅(t⋅d)+r}{d}=kt+\dfrac{r}{d}\\\because x\in \N\\\therefore d\mid r\\\therefore d\mid (a\bmod b)\\\therefore a\bmod b 的因数集与a与b的公因数集相同\\\therefore \gcd(a,b)=\gcd(b,b\bmod a)此算法也常称为辗转相除法。
123456789101112131415#include<bits/stdc++.h>using namespace std;int a,b...
整除分块首先引入一个问题,若我们要求这么一个式子:
\sum\limits_{i=1}^{n} \left\lfloor\dfrac{n}{i}\right\rfloor自然而然会想到这么一段翻译代码:
12for(int i=1;i<=n;i++) sum+=n/i;
但是,如果 $1\le n\le10^9$,又该如何解决呢?
显然,$\left\lfloor\dfrac{n}{i}\right\rfloor$与$\dfrac{n}{i}$的不同在于,前者的值在某些情况下会出现区间性的大量重复。下面我们来考察当 $n=10$时$\left\lfloor\dfrac{n}{i}\right\rfloor$的取值
\boxed{10}\quad \boxed{5}\quad \boxed{3}\quad \boxed{2\quad 2}\quad \boxed{1\quad 1\quad 1\quad 1\quad 1}我们可以发现:
\left\lfloor\dfrac{n}{1}\right\rfloor=10\\
~\\
\left\lfloor\dfrac{...