869.试除法求约数
注意点：
1.试除法就是让i遍历的最大值到a/i。
2.约数成对存在，只遍历前一部分即可。
代码：
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
priority_queue<int,vector<int>,greater<int>> qu;
void get(int a){
for(int i = 1;i<=a/i;++i){
if(a%i==0)
{
qu.push(i);
if(i!=a/i){
qu.push(a/i);
}
}
}
}
int main (){
int n;scanf("%d",&n);
while(n--){
int a;scanf("%d",&a);
get(a);
while(!qu.empty()){
printf("%d ",qu.top());qu.pop();
}puts("");
}
return 0;
} 约数个数与约数之和
870.约数个数
分为两个部分：
1.求质因子及其次数，通过a/=i i<=a/i求得
2.求得的次数放在unordered_map中，非常好的工具，可以之际用auto p:map遍历。
3.求解的公式如上
代码：
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
using namespace std;
unordered_map<int,int> ma;
typedef long long ll;
const int mod = 1e9+7;
int main (){
int n;cin>>n;
while(n--){
int a;scanf("%d",&a);
for(int i = 2;i<=a/i;++i){
while(a%i==0){
a/=i;
ma[i]++;
//cout<<i<<endl;
}
}
if(a>1){
ma[a]++;
// cout<<a<<endl;
}
}
ll res =1;
for(auto p:ma){
res = res*(p.second+1)%mod;
}
cout<<res;
return 0;
} 871.约数之和
方法一样，先分解质因数，将分解后的结果存入map中
在按照公式求解
关键的一点就是，long long 的数据相乘与取模。很容易出错，很容易越界。注意y总的处理。如何处理 
。
每一次乘以n再加一。
1
n+1
n(n+1)+1 = n^2 +n+1
n(n(n+1) +1= n^3+n^2+n+1
……
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
using namespace std;
const int mod = 1e9+7;
unordered_map<int,int> ma;
typedef long long ll;
int main (){
int n;scanf("%d",&n);
while(n--){
int a;scanf("%d",&a);
for(int i = 2;i<=a/i;++i){
while(a%i==0){
a/=i;
ma[i]++;
}
}
if(a>1)ma[a]++;
}
ll ou = 1;
for(auto p:ma){
ll di = p.first;
ll zhi =p.second;
ll nu = 1;
for(int i = 1;i<=zhi;++i){
nu =(nu*di+1)%mod;
}
ou = nu*ou%mod;
}
printf("lld",ou);
return 0;
} 872.辗转相除法（欧几里得法）求最大公约数
题解详见：
https://www.acwing.com/solution/content/145791/
不用担心输入的a小于b，如果小于b 则在运算中会先将其交换，再辗转相除。
左边存大的，右边存小的。每一次相除完，将左边剔除，右边左移。%运算后的c填补右边的空。直至右边为0为止，则最大公约数就是左边的数。
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
using namespace std;
int main (){
int n;cin>>n;
while(n--){
int a,b;scanf("%d%d",&a,&b);
//左边放大的，右边放小的
//相除完后，右边左移，余数上右边，再相除，直至右边为0
while(b){
int c = a%b;
a = b;
b = c;
}
cout<<a<<endl;
}
return 0;
}
//递归形式
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
int gc(int a,int b){
if(b==0){
return a;
}
return gc(b,a%b);
}
int main (){
int n;cin>>n;
while(n--){
int a,b;cin>>a>>b;
int x;int y;
cout<<gc(a,b)<<endl;;
}
return 0;
} 877.扩展欧几里得法求最大公约数及其系数
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;
int gc(int a,int b,int &x,int &y){
if(b==0){
x = 1;
y = 0;
return a;
}
int d = gc(b,a%b,x,y);
int x2 = x;
int y2 = y;
y = x2-(a/b)*y2;
x = y2;
return d;
}
int main (){
int n;cin>>n;
while(n--){
int a,b;cin>>a>>b;
int x;int y;
gc(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
} 
