贴上之前写的笔记以及刚刚AC的代码

约数个数

显示直接相乘然后求质因数并不合适，考虑到算数基本定理
$$ N=p_1^{a_1}p_2^{a_2}\ldots p_m^{a_m} $$
例如 12，其质因数是 2,3。

其约数必然由其质因数的次幂组成的，有1，2，3，4，6，12
$$ \begin{align*} &1=2^0*3^0\\ &2=2^13^0\\ &3=2^03^1\\ &\ldots\\ &12=2^23^1 \end{align*} $$
其中12可以分解为质因数乘积 $2^23^1$，因此2的幂可以取 $0\sim 2$ 共3种， 3的幂可取 $0\sim 1$ ，共2两种，因此有6个约数

综上可得，约数个数是
$$ Num=\prod_{i=1}^m(a_m+1) $$

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=2e8+10;
typedef long long ll;
const ll mod=1e9+7;
map<int,int>mp;
ll get(ll x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            int cnt=0;
            while(x%i==0){
                x/=i;
                cnt++;
            }
            mp[i]+=cnt;
        }
    }
    if(x>1)mp[x]+=1;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        get(x);
    }
    ll res=1;
    for(auto e:mp){
        res=res*(e.second+1)%mod;
        //cout<<e.first<<" "<<e.second<<endl;
    }
    cout<<res<<endl;
}

约数之和

如果 $N=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}$

约数个数 $(c_1+1)(c_2+1)\ldots (c_k+1)$

约数之和 $(p_1^0+p_1^1+\ldots+p_1^{c_1})\ldots(p_k^0+p_k^1+\ldots p_k^{c_k})$

对于等比数列求和，可采用

$t=t*a+1$

证明
$$ \begin{align*} &t=a+1\\ &t=(a+1)a+1=a^2+a+1\\ &t=a^k+a^{k-1}+\ldots +1 \end{align*} $$

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=2e8+10;
typedef long long ll;
const ll mod=1e9+7;
map<int,int>mp;
ll get(ll x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            int cnt=0;
            while(x%i==0){
                x/=i;
                cnt++;
            }
            mp[i]+=cnt;
        }
    }
    if(x>1)mp[x]+=1;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        get(x);
    }
    ll res=1;
    for(auto e:mp){
        ll p=e.first,n=e.second;
        ll temp=1;
        while(n--)temp=(temp*p+1)%mod;
        res=res*temp%mod;
    }
    cout<<res<<endl;
}