（本篇并不适合初学者看）
1.定义：
若d能整除n，则d是n的约数，记为d|n
2.寻找
试除法：
约数成对出现（除了n是一个完全平方数）
根号n试除，能整除的就是一个约数。然后另一半也直接算上。
for(int i=1;i*i<=x;i++){ if(n%i==0){ factor[++tot]=i; if(i!=n/i) factor[++tot]=n/i; } }
但是这样可能稍慢。
一个数的约数，从质因数分解的情况下来看，
n=p1^q1*p2^q2*....
根据乘法原理，约数个数就是：(q1+1)*(q2+1)*....
所以，可以直接质因数分解，
然后dfs搜出来所有因数。
这样，质因数分解的时候，可以
while(x%i==0)x/=i
这样，质因数分解上限是根号n，但不是严格根号n的。
然后dfs是约数个数复杂度的。
int yue[N],num; int zhi[N],tot,cnt[N]; void dfs(int x,int now){ if(x==tot+1){ yue[++num]=now; return; } int tmp=1; for(int i=0;i<=cnt[x];i++){ dfs(x+1,now*tmp); tmp*=zhi[x]; } } void divi(int x){ for(int i=2;(long long)i*i<=x;i++){ if(x%i==0){ zhi[++tot]=i; while(x%i==0){ cnt[tot]++; x/=i; } } } if(x>1) zhi[++tot]=x,cnt[tot]=1; }
试除法推论：一个数的约数个数上界是$2 imessqrt{n}$
但是试除法好写啊。。
巧妙利用每个数约数，找到从n个数中选择k个数的最大公约数。
*1~N约数个数总和
考虑1~n的数能作为哪些数的约数
sum=n/1+n/2+n/3+...n/n=nlogn
3.筛法：从质因数分解方面考虑
筛法中转移只有两种情况：
pri[j]是i的最小质因子
pri[j]比i的最小质因子还小
①约数个数
设c[i]表示i最小质因子次数
f[i]表示i约数个数。
②约数和
$sum=(1+p_1+p_1^2+...+p_1^q1)*...*(1+p_k+p_k^2+...+p_k^qk)
设c[i]表示，i最小质因子的贡献。即：(1+p_1+p_1^2+...+p_1^q1)（假设p1是最小质因子）
设f[i]表示i约数和。
具体转移见：
SIEVE 线性筛
4.最大公约数gcd
前置：裴属定理：
若gcd(a,b)=1,则存在x，y，使得x*a+y*b=1
所以也存在x,y, 使得x*a+y*b=gcd(a,b)
扩展一下：
整数a1,a2,...,an
存在x1,x2,..xn使得,x1*a1+x2*a2+..+xn*an=gcd(a1,a2...,an)
求法：
①辗转相减法，高精gcd
直接无脑减肯定太慢。
A，B
如果A为偶数，B为奇数，先把A除以2除成奇数。因为肯定没有2这个因子了。
同理，如果B为偶数，A为奇数，也这样。
如果A，B同为偶数，把2不断提出来，乘进gcd，直到一个变成奇数。
如果A，B同为奇数，直接gcd(A,B)=gcd(A,A-B)其中，A>=B
奇数相减一定出偶数，还可以再/2
这样，平均的复杂度也是log级别的。
②欧几里得算法
gcd(a,b)=gcd(b,a%b)
证明：对于d|a,d|b,d|gcd(a,b)
设b=q*a+r, r=a%b
所以，d|q*b,
所以，d|(a-q*b)=r
所以，对于a，b所有的公约数，也是r的约数，所以，最大公约数也一定是b,r的最大公约数。
③扩展欧几里得算法exgcd
裴属定理告诉我们，x*a+y*b=gcd(a,b)有解
可以计算x*a+y*b=gcd(a,b)
x，y的一组解和通解。
EXGCD 扩展欧几里得
（最小公倍数）
④一些性质：
1.gcd(Fibo[n],Fibo[m])=Fibo[gcd(n,m)]
2.gcd(a1,a2,...,an)=1 等价于：
$sum_{d|ai}space mu(d) =1
如果答案不是1，gcd就不是1，就不互质。
证明：
对于两个数i，j
i，j互质的时候，公约数只有1，u(1)=1
i，j不互质的时候，公约数就是i，j最大公约数的约数。
设gcd(i,j)=p1^q1*p2^q2*...pk^qk
那么，如果取两个以上的pi,u就是0，不影响答案。
所以，就是取p1、。。。pk一个或不取的方案数要考虑
取零个：C(k,0)个1
取一个 ：C（k,1）个-1
取两个 ：C(k,2)个1
。。。
所以，最后的答案是：C(k,0)-C(k,1)+C(k,2)-C(k,3)+...+C(k,k)
根据组合数的性质，不论k是奇数还是偶数，答案都是0
证毕。
最大公约数与最小公倍数——质因数分解考虑法。
例题：Hankson的趣味题
5.互质与欧拉函数。
①定义：phi(i)表示，1~i中和i互质的数的个数。
公式：phi(i)=n*(1-1/p1)*(1-1/p2)...(1-1/pk)p是质因子。
可以容斥原理证明：n-n/p1-n/p2+n/(p1*p2)。。。
②欧拉函数性质
1.任意的n>1,1~n中和n互质的数的总和为$n*phi(n)/2$
证明：
因为gcd(n,x)=gcd(n,n-x)所以，如果x和n互质，那么n-x也和n互质
互质的数成对出现（即$phi(i)$都是偶数，除了$phi(2)$）。平均值是n/2，所以总和是$n*phi(n)/2$
2.若a，b互质，则$phi(ab)=phi(a) imes phi(b)$
根据公式，质因数分解，两边的质因子都是互不相同的，恰好可以拼成ab欧拉函数的值。
3.$sum_{d|n} space phi(d) = n$
证明：
（网上证明有很多，这里说一下我的伪证明）
我的感觉是，好像把所有的约数的phi加在一起就是n的话，
也就是说，与约数d互质的所有数，应该能乘上一个数，一起覆盖完1~n
对于所有属于1~n的一个数x，设gcd(n,x)=g
那么，n/g与x/g一定互质。
那么，与n的gcd都为g的所有的x，其个数就是$phi(n/g)$
对于一个x，其和n的gcd唯一。
而对于n的一个约数d，n/d也是唯一的，
这里，gcd和n/d其实就是相同的。
那么，我们可以找对于所有的n的约数g,
与n的最大公约数为g的数，可以唯一对应一些x
那么，我们枚举所有的约数g，就对应完了所有的x也就是1~n
而n/g也是n的一个约数，
所以可以说，$sum_{d|n} space phi(d) = n$
③欧拉函数寻找：根据定义即可。
也是直接的试除法根号n分解。
int phi(int n){ int ret=n; for(int i=2;i*i<=n;i++){ if(n%i==0){ ret=ret/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ret=ret/n*(n-1); return ret; }
④欧拉函数筛法
把定义稍微变一下形，
phi(i)=n*(1-1/p1)*(1-1/p2)...(1-1/pk)
如果我们把n质因数分解，那么其实就是：
$(p_1^q1-p_1^{q1-1})*....*(p_k^qk-p_k^{qk-1})$
所以现在，
直接通过定义筛即可。
如果pri[j]和i互质，那么$phi(i*pri[j])=phi(pri[j]) imes phi(i)$积性函数的性质。
如果pri[j]和i不互质，那么$phi(i*pri[j])=phi(i) imes pri[j]$次数多了一个1
例题：仪仗队
总结：
约数的考察主要对于gcd，和互质的欧拉函数。
约数的很多性质都可以用质因数分解表示和解释。
对于后面的同余，有着奠基的意义。