约数
如果一个整数n能除以整数d余数为0，那么d就是n的约数，又称因数，n就是d的倍数，那么如何求去一个数n的所有约数呢？
1.试除，首先我们知道约数，总是成对出现的，一个数d是n的，那么n/d也是这个数n的约数，除非完全平方数
int fd[1000],m=0;
for(int i=1;i<=n;i++)
{
if(n%i==0)
{
f[++m]=i;
if(i!=n/i) f[++m]=n/i;//完全平方数特殊判断
}
}
2.若用试除法来求n的每一个数是否为n的约数，太过于浪费时间，时间复杂度过高，必须得进行一个优化。我们可以反过来考虑每一个数，对于每一个数d，1~N中以d为约数的数就是d的倍数d,2d,3d。所以，使用倍数法来进行求取
vector <int> f[5000];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n/i;j++)
f[i*j].push_back(i);//全部保存倍数
for(int i=1;i<=n;i++)
{
for(int j=0;j<f[i].size();j++)
{
cout<<f[i][j]<<" ";
}
}
}
最大公约数
其实这些东西的概念我们并不陌生。
其实就是说，两个数的公共的因数中最大的那个数。
那么我们定义两个数gcd（a,b）为两个数的最大公因数，lcm（a,b)就是两个数的最小公倍数。那么就有下面的公式：
gcd(a,b)*lcm(a,b)=a*b
所以依据这个我们就可以求出来了，这里运用到辗转相除法，不再一一讲述了
gcd(a,b)=gcd(b,a%b)
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int lcm(a,b)
{
int gcdd=gcd(a,b);
return a*b/gcdd;
}//lcm*gcd=a*b
互质
如果两个数gcd(a,b)=1，说明a，b互质
gcd(a,b)=gcd(b,c)=gcd(a,c)=1 就叫做两两互质
欧拉函数
1~n中与n互质的数的个数，叫做欧拉函数
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))……(1-1/p(n))
φ(10)=10×(1-1/2)×(1-1/5)=4
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
φ(49)=49×(1-1/7)=42;
long long eular(long long n)
{
long long ans=n;
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);//统计个数
while(n%i==0)
n/=i;//去除
}
}
if(n>1) ans=ans/n*(n-1);//特判
return ans;
}
至于为什么ans=ans/i*(i-1)，其实这里就是一个小小的化简，展开来其实就是ans=ans*(1-1/i)，只是考虑到分数之间的运算，所以用以一个化简
ans×(1-1/i)
=ans-ans/i
=i×ans/i - ans/i
=i×ans-ans/i
=(i-1)×ans/i
欧拉函数的性质：
1~n中与n互质的数的和为n×φ(n)/2
如果a，b互质，那么φ(ab)=φ(a)φ(b)
