约束个数

任何一个数都可以表示成:
N = p1^a1p2^a2p3^a3....pk^ak;
故它的任何一个约数都可以表示为
d= p1^b1*p2^b2.....pk^bk;
b1 可取 0-a1;
b2 可取 0-a2;
故一共有(a1+1)(a2+1)…(ak+1)个约数
https://www.acwing.com/problem/content/872/
代码:

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main()
{
    int n;
    cin>>n;
    ll res=1;

    unordered_map<int,int>primes;  //存每个质因子和它的次数
    while(n--)
    {
        int a;
        cin>>a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                while(a%i==0)
                {
                    primes[i]++;
                    a/=i;
                }
            }
        }
        if(a>1)primes[a]++;
    }
    for(auto t:primes)res=res*(t.second+1)%mod;
    cout<<res<<endl;
    return 0;
}

约束之和

同样的，任何一个数都可以表示为
N=p1^a1*p2^a2....pk^ak;
它约数的所有和就是p1..pk并且再分别在0-a1,0-a2,0-ak中组合
故个数为
(p1^0+p1^1+.....p1^a1)(p2^0+p2^1+.....p2^a2)…(pk^0+pk^1+....pk^ak)
https://www.acwing.com/problem/content/873/

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int main()
{
    int n;
    cin>>n;
    unordered_map<int,int>primes;
    while(n--)
    {
        int a;
        cin>>a;
        for(int i=2;i<=a/i;i++)
        {
            while(a%i==0)
            {
                primes[i]++;
                a/=i;
            }
        }
        if(a>1)primes[a]++;
    }
    ll res=1;
    for(auto t:primes)
    {
        ll cnt=1;
        int p=t.first,b=t.second;
        while(b--)cnt=(cnt*p+1)%mod;
        //第一次cnt=p+1  %mod
        //第二次cnt=(p+1)*p+1 = p^2+p+1      %mod;
        /第三次 cnt=((p+1)*p+1)p+1=p^3+p^2+p+1   %mod;
        res=res*cnt%mod;
    }
    cout<<res<<endl;
    return 0;

}

最大公约数

根据整除的性质 若a|b, a|a+b ,a|na+mb;
gcd(a,b) 等价于gcd(b,a%b)
设d|a,d|b
a%b=a-kb其中k=a/b;
d|b,d|a,故d|a-kb;
故d也是（b,a%b）公约数
代码

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

快速幂

求a^b;
首先需要将a^(2^0),a^(2^1),a^(2^2)…a^(2^logb)求出
由递推可知 a^(2^i)=a^(2^(i-1))a^(2^(i-1))
然后a^b=a^(2^a1)a^(2^a2)*…a^(2^ak)
b可以用二进制表示;
如5可以表示为101;
判断如果末尾是1则乘相应的a的幂指数
代码如下

#include<iostream>
typedef long long ll;
using namespace std;
int get(int a,int k,int p)
{
    ll res=1%p;
    while(k)
    {
        if(k&1)res=res*a%p;
        k>>=1;
        a=a*(ll)a%p;
    }
    return res;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        cin>>a>>b>>p;
        cout<<get(a,b,p)<<endl;
    }
    return 0;
}。