[number theory] divisor

Try division to find the divisor

subject

Activities - AcWing 

explain

• Because divisors appear in pairs , So you just need to i*i<=x
• prevent x It's a total square , One more number is recorded . Therefore, special deposit is required x/i Conditions

Code segment

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>get_divisors(int x)
{
    vector<int>ans;
    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;
         vector<int>ans=get_divisors(x);
         for(auto x:ans)cout<<x<<' ';
         cout<<endl;
     }
     return 0;
}

Find the number of divisors

subject

Activities - AcWing

explain

•  
• According to the above theorem , We should factorize each number , Then find the sum of prime factors
• be aware 1 Although it is a divisor , But the combination result is only 1 Kind of , So it's not in the scope
• about ans The multiplication modulus of cannot be written as ans*=x%mod, It can only be written as ans=ans*x%mod

Code segment

#include<iostream>
#include<unordered_map>

const int mod=1e9+7;

using namespace std;
unordered_map<int,int>primes;
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<<ans%mod<<endl;
    
}

The sum of the approximations

subject

Activities - AcWing 

explain

• Here, please a1^α1 Sum of divisors of , It is obvious that there can be algebraic theorems
• Multiplication principle , It can be understood as the sum of each power combination of each prime number
• Select a number in each bracket and multiply it to exactly equal one of the divisors
• This does not repeat the choice of accumulation , That is, the sum of approximations  
• When finding the sum of divisors of prime numbers , For the accumulation of proportional series
• The simple formula is

int t( frequency ） ,x( base number ）,sum( and ）

while(t--)

{

sum=sum*x+1;

}

Code segment

#include<iostream>
#include<unordered_map>
const int mod=1e9+7;
using namespace std;
int main()
{
    int t;cin>>t;
    unordered_map<int,int>primes;
    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;
         // Although it can guarantee tmp No more than mod, But if sum*tmp It is likely to be greater than mod
     }
     cout<<sum<<endl;
  
}

greatest common divisor

subject

  Activities - AcWing

explain

• Mathematical proof of Euclidean algorithm
• 【 number theory 】 Euclid algorithm _nathanqian123 The blog of -CSDN Blog

#include<iostream>
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<<gcd(a,b)<<endl;
    }
}