1.求解一个数的约数

试除法：
时间复杂度为O(sqrt(n))

//试除法求约数
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>get_yueshu(int x){
    vector<int>res;
    for(int i=1;i<=x/i;i++){
        if(x%i==0){           //只枚举小的那个约数
            res.push_back(i);
            if(i!=x/i){       //如果大的约数和小的约数不一样，就存入数组中，否则不存入
                res.push_back(x/i);
            }
        }
    }
    sort(res.begin(),res.end());
    return res;
}
int main(){
    int n;

    cin>>n;
    int x;
    while(n--){
        cin>>x;
        vector<int>T=get_yueshu(x);
        for(auto t:T){
            cout<<t<<' ';
        }
        cout<<endl;
    }
    return 0;
}

2.求解约数的个数
X=p1^a1p2^a2…………pk^ak;
对于每一个pi^ai都有：
pi^0、pi^1…………pi^ai个质因子，所以质因子的个数ans=(0+1+2……+ai)=ai+1
所以X的约数有(a1+1)(a2+1)…………(ak+1)个
其实就是排列组合，看这些质因子有多少中排列情况
举例：
218=36，2=2^1, 18=2^13^2
所以36=2^23^2;
36的约数为 (2+1)*(2+1)=9,即 1 2 3 4 6 9 12 18 36

代码：

对于该题使用了没有使用过的map，详情： [map函数使用方法](https://blog.csdn.net/weixin_43828245/article/details/90214494) 
函数中不能有重复的键，但是可以有相同的键值，并且在该题目的插入中，因为质因子i不确定
所以选择primes[i]++的方式，每存入一个键为i，键值就++

#include<iostream>
#include<map>
using namespace std;
long long res=1;
const int N=1e9+7;
map<int,int>primes;

int main(){

    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            if(x%i==0){
                int k=0;
                while(x%i==0){
                    x=x/i;
                    primes[i]++;
                //primes.insert(pair<int,int>(i,++k));
                    }
            }
        }
        if(x>1)
        primes[x]++;
    }
    for(map<int,int>::iterator t=primes.begin();t!=primes.end();t++){
        res=res*(t->second+1)%N;
    }
    cout<<res;
    return 0;
}

3.求解一个数的约数和
在这里学到了用 auto去遍历map函数十分的简便
另外一个就是秦九韶算法，真的绝了
关于这个算法在22年寒假每一一题的笨拙的手指中听y总讲过，那会就感觉很精妙
但是没有深入去研究，今天在听约数和的时候再次惊讶秦九韶算法的精妙
这里：借用大佬的讲解
如果 N=p1^c1∗p2^c2∗…∗pk^ckN=p1^c1∗p2^c2∗…∗pk^ck
约数个数：(c1+1)∗(c2+1)∗…∗(ck+1)(c1+1)∗(c2+1)∗…∗(ck+1)
约数之和： (p1^0+p1^1+…+p1^c1)∗…∗(pk^0+pk^1+…+pk^ck)

算约数和的话需要求解出每一个质因子从其指数为0一直到他在x中出现的最大次数的和
然后各个相乘。
我的思路是利用pow()函数，代码如下：

 /*for(map<int,int>::iterator t=primes.begin();t!=primes.end();t++){
        int f=t->first;
        long long res=0;
        for(int i=0;i<=t->second;i++){
            res+=pow(f,i)%N;     //N=1e9+7

        }
        sum=sum*res%N;
    }
    cout<<sum;
    */

然后数小的时候结果正确，但是当数大的时候就会出现问题，原因在于
1.pow()函数的返回值是double类型而非int类型
2.他这个mod 1e9+10这里在式子中会出现问题所以不管怎样变化他就是有问题
通过看别的伙伴的思路，他们提出使用等比数列求和的方法也出现了问题
因为不知道是先mod 1e9+10还是先加再mod,这样精度啥的会出现问题，
然后看视频讲解时，y总用了秦九韶算法解决这个问题，简直目瞪口呆
t=t∗p+1
t=1
t=p+1
t=p2+p+1
……
t=pb+pb−1+…+1
太神奇了

还有b进制转化为十进制的题目
代码：

int get(string s,int b){
//b进制函数转化为十进制
    int x=0;
    int i=0;
   /* for(auto c: s){
         x=x*b+c-'0';
    }*/
    while(i<s.size()){
        x=x*b+s[i]-'0';
        i++;

    }
    return x;
}

就是一串式子进行化简成这个样子，找规律确定各个值
好了上代码吧！

#include<iostream>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e9+7;
map<int,int>primes;
int main(){

    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x=x/i;
                primes[i]++;
            }
        }
        if(x>1){
            primes[x]++;
        }
    }

    long long res=1;
    for(auto t:primes){        //用auto遍历，convenience
        int p=t.first;
        int d=t.second;
        long long sum=1;
        while(d--){
            sum=(sum*p+1)%N;

        }
        res=res*sum%N;
    }
    cout<<res;
    return 0;
}

4.欧几里得求最大公约数

直呼精辟啊！
证明如下：
有数字a,b;那么a、b的最大公约数等价于(b,a mod b)，注意顺序，就是大的那一方在第一个数的位置
小的那一方在第二个数的位置，如此循环往复直至第二个数为0，此时结束，第一个数也就是两者的最大公约数
为什么上边两个式子是等价的呢，因为
假设d是a,b的最大公约数，d|a, d|b ,那么d|ax+by
a mod b=a-kb,k是a/b下取整，成立
从左往右推：因为d|a, d|b，所以d|a-kb
从右往左推：因为d|a-kb ，d|b 现证明：d|a :
d|a-kb +k*b = d|a 成立

代码：

#include<iostream>
using namespace std;
int gcd(int a,int b){
    if(b!=0){
        return gcd(b,a%b);
    }
    else{
        return a;
    }
}
int main(){

    int n;
    cin>>n;
    int a,b;
    while(n--){
        cin>>b>>a;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}