先做回顾
1、什么是约数？
在数学中，一个数的约数（Divisor）是能够整除这个数的所有正整数。换句话说，如果一个正整数 d 能够被另一个正整数 n 整除，那么 d 就是 n 的一个约数。
2、算术基本定理——唯一分解定理
它指出，每个大于1的自然数都可以唯一地表示为若干个质数的乘积，而且这些质数的次序是不重要的。换句话说，质因数分解是唯一的，除了质因数的顺序之外。
算术基本定理包含两个部分：
- 存在性：每个大于1的自然数都可以分解为质数的乘积。
- 唯一性：这种分解是唯一的，不考虑质因数的顺序。
例如，数字60可以分解为质数的乘积：60=2^2×3^1×5^1。这是60的唯一质因数分解，尽管我们可以改变质因数的顺序，例如写成 60=5^1×3^1×2^2，但这仍然被认为是相同的分解。
3、除、除以、除数、被除数
a除b=b/a，a除以b=a/b，当x/y时x是被除数，y是除数
4、C++ STL里的哈希表(unordered_map)。unordered_map 是 C++ 标准库中的一个关联容器，它提供了一种基于哈希表的关联容器实现。unordered_map允许以平均常数时间复杂度（O(1)）访问容器中的元素，这比传统的基于红黑树实现的map容器（平均时间复杂度为 O(log n)）要快。
unordered_map<int,int> hash;第一个int存储的是键，后者存储的是对应键的值。其中键是唯一的，值可以是任意。若想插入值：hash.insert({1,2})或者hash[1]=2,都表示插入键值对 (1, 2)，键：1，值：2。
5、for(auto hash1:hash) 表示遍历该哈希表中的每一个键值对。若不想遍历完，只是遍历到某一特定值k时可以for (auto it = prime.begin(); it != prime.find(k); ++it) { ... }。当然，如果想从某一特定的值开始遍历时（假设为m），则可以初始值auto it=prime.find(m)。此外，这里的auto可以替换为pair<int,int>类型。
思路：
求出来约数，sort一下即可，具体见代码。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int a[100010],b[100010],ans,cnt;
/*
由于约数是成对出现的，所以只需要求出较小的那一方，然后直接计算出另一方即可
比如求出8的一个约数为2，那么另一个约数自然为8/2=4。
*/
void get_factor(int u)
{
for(int i=1;i<=u/i;i++)
{
if(u%i==0)
{
a[ans++]=i;
if(i!=u/i)
a[ans++]=u/i;
}
}
sort(a,a+ans);
for(int i=0;i<ans;i++) cout << a[i] << " ";
cout << endl;
return;
}
int main()
{
cin >> n;
while(n--)
{
int x;
cin >> x;
memset(a,0,sizeof a);
ans=0;
get_factor(x);
}
return 0;
}
约数个数与约数之和
由算数基本定理可得：任何一个数N都可以表示为：
其中p1,p2,…,pk 是质数，e1,e2,…,ek 是对应的指数。
那么求解约数的个数的公式为：(e1+1)*(e2+1)*......*(ek+1)
证明：
求约束的个数，也就是从上述不同质因子里边挑出来一个值，那么排列组合即可得证。
贴一张：
不难发现约数之和的公式为：(p1^0+p1^1+...+p1^e1)*(p2^0+p2^1+...+p2^e2)*...*(pk^0+pk^1+...+pk^ek)。后续题目里会模拟样例，瞟一眼模拟就明白了
用试除法求出质因子的底数与质数，然后带一下公式即可
代码：
//int范围内，约数最多的个数在1500左右
#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
const int mod=1e9+7;
int main()
{
int n;
cin >> n;
unordered_map<int,int> prime;
while(n--)
{
int x;
cin >> x;
/*
这里边输入边取出x的底数与指数，而不是先乘出结果再对质因数进行取底数与指数
1、先计算完乘的结果是没有必要的，因为每个数对应的质因数的底数相同。
比如：计算8*16*14的约数个数
①若先乘完结果：1729=2^8*7^1,那么对应的约数的个数就是(8+1)*(1+1)=18。
②若非如此：先将8的质因数取底数与指数：prime[2]=3（这里会自加三次，因为8=2^3）。
然后将16的质因数取底数与指数：prime[2]=7（在前者8的基础上又自加了四次,16=2^4）。
最后操作14：prime[2]=8,prime[7]=1。那么循环遍历后就会得到质因数2的指数为8，7的指数为1
最后套用公式即可求解。
2、若先乘完，必然会爆int（题目一定不会让你那么轻松(⊙o⊙)），所以不得不采用第二种方法。
*/
for(int i=2;i<=x/i;i++)
{
while(x%i==0)
{
x/=i;
prime[i]++;
}
}
if(x>1) prime[x]++;
}
long long res=1;
for(auto primes:prime) res=res*(primes.second+1)%mod;
cout << res;
return 0;
}
代码：
/*
模拟一下样例：上述的约数个数可分解为：2^5*3^1=96（这里可以手动求，也可以用867的代码求）
那么它的约数就是:1 2 3 4 6 8 12 16 24 32 48 96 （试除法求约束）
也就是:2^0*3^1+2^1*3^1+2^2*3^1+2^3*3^1+2^4*3^1+2^5*3^1+2^0*3^0+2^1*3^0+2^2*3^0+2^3*3^0+2^4*3^0+2^5*3^0
即3+6+12+24+48+96+1+2+4+8+16+32，也就是(2^0+2^1+2^2+2^3+2^4+2^5)*(3^0+3^1)
我们可以发现约数之和=每个质因数的和相乘（这里的和即是等比数列的求和）
*/
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<cmath>
using namespace std;
const int mod=1e9+7;
int n;
int main()
{
cin >> n;
unordered_map<int,int> prime;
while(n--)
{
int x;
cin >> x;
for(int i=2;i<=x/i;i++)
{
while(x%i==0)
{
x/=i;
prime[i]++;
}
}
if(x>1) prime[x]++;
}
long long res=1;
for(auto primes:prime)
{
int a=primes.first,b=primes.second;
long long t=1;
//这里等比求和用秦九韶公式，因为秦九韶是相乘，不涉及除运算
while(b -- ) t=(a*t+1)%mod;
res=res*t%mod;
}
cout << res;
return 0;
}
欧几里得——辗转相除法
如果a,b的最大公约数为d那么gcd(a,b)=gcd(b,a mod b)
证明：d | a（d整除a）、d | b 那么就有d | (a+b)、d | (x*a+y*b)。
充分性：当d | a，d | b时（假设(a,b)的最大公约数为：d）
要证充分性，我们需要证明(a,b)的最大公约数d为(b,a mod b)的最大公约数
a mod b=a-(a/b)*b（这里括号里取整），设常数c=(a/b)，那么就有a mod b=a-c*b，那么根据d | (x*a+y*b)，而此时令x=1，y=-c所以可得：d | (a mod b)，又因为d | b所以d为(b,a mod b)的最大公约数
必要性：当d | b、d | a mod b 时（假设(a,b)的最大公约数为：d）
要证充分性，我们需要证明(b,a mod b)的最大公约数d为(a,b)的最大公约数
a mod b=a-(a/b)*a，设常数c=(a/b)，那么就有a mod b=a-c*b，因为d | b所以d | (x*b+y*(a mod b))这里令x=c y=1则有d | (c*b+a-c*b)→d | a 所以d | a又因为d | b 所以d为gcd(a,b)的最大公约数。
则gcd(a,b)=gcd(b,a mod b)得证
代码：
//欧几里得算法——辗转相除法
#include<iostream>
#include<cstring>
using namespace std;
int n;
int gcd(int a,int b)
{
//当b等于0时，最大公约数就为a。不等于0时，进行递归寻找最大公约数
return b?gcd(b,a%b):a;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int a,b;
cin >> a >> b;
printf("%d\n",gcd(a,b));
}
return 0;
}