欧几里得算法\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{...