【数论】约数

活动 - AcWing 

因为约数都是成对出现，所以只需要i*i<=x防止x是完全平方数，多记录了一个数字。所以需要特判存入x/i的条件 代码段

#include
#include
#include
using namespace std;
vectorget_divisors(int x)
{
    vectorans;
    for(int i=1;i*i<=x;i++)
    {
        if(x%i==0)
        {
        ans.push_back(i);
       if(i!=x/i)ans.push_back(x/i);
        }
    }
    sort(ans.begin(),ans.end());
    return ans;
}
int main()
{
     int t;
     cin>>t;
     while(t--)
     {
         int x;cin>>x;
         vectorans=get_divisors(x);
         for(auto x:ans)cout< 
 
求约数个数 
题目 
 
活动 - AcWing
 
解释 
 根据如上定理，我们应该对于每个数进行质因数分解，然后求质因数的总和注意到1虽然是约数，但组合结果只有1种，所以不在范围内对于ans的乘法取模时不能写成ans*=x%mod，只能写成ans=ans*x%mod
代码段 
#include
#include

const int mod=1e9+7;

using namespace std;
unordered_mapprimes;
int main()
{
    int n;cin>>n;
    while(n--)
    {
    int x;cin>>x;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            while(x%i==0)
            {
             primes[i]++;
             x/=i;
            }
        }
    }
    if(x>1)primes[x]++;
    }
    long long ans=1;
   for(auto it=primes.begin();it!=primes.end();it++)
   {
       ans=ans*(1+it->second)%mod;
   }
    cout<
 
 
约数之和 
题目 
 
活动 - AcWing 
 
解释 
 
这里求a1^α1的约数之和，是可以有代数定理显然得出乘法原理，可以理解成各个质数的各个次幂组合之和每一个括号内选择一个数然后相乘正好等于其中一个约数这样不重复的选择累加，即约数之和 求质数的约数之和时，对于等比数列的累加简单的公式为
 
 
int t(次数） ，x(底数），sum(和）
 
 
while(t--)
 
 
{
 
 
sum=sum*x+1;
 
 
}
 
 
代码段 
#include
#include
const int mod=1e9+7;
using namespace std;
int main()
{
    int t;cin>>t;
    unordered_mapprimes;
    while(t--)
    {
        int x;cin>>x;
        for(int i=2;i*i<=x;i++)
        {
            if(x%i==0)
            {
                while(x%i==0)
                {
                    primes[i]++;
                    x/=i;
                }
            }
            
        }
        if(x>1)primes[x]++;
    }
     long long sum=1;
     for(auto it=primes.begin();it !=primes.end();it++)
     {
         long long tmp=1;
         int t=it->second;
         while(t--)
         {
             tmp=(tmp*it->first+1)%mod;
         }
         sum=sum*tmp%mod;
         //虽然能保证tmp不大于mod，但如果sum*tmp很有可能大于mod
     }
     cout< 
 
最大公约数 
题目 
 
 活动 - AcWing
 
解释 
关于欧几里得算法的数学证明【数论】欧几里得算法_nathanqian123的博客-CSDN博客
#include
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        cout<