Unique Factorization Theorem 870. Number of Divisors

Hits: 0

approximate number

  1. Number of Divisors
    Given n positive integers ai, please output the number of divisors of the product of these numbers, and the answer is modulo 109+7.
    Input format
    The first line contains the integer n.
    The next n lines each contain an integer ai.
    Output Format
    Output an integer that represents the number of divisors of the product of the given positive integers. The answer needs to be modulo 109+7.
    Data range
    1≤n≤100,
    1≤ai≤2×109
    Input sample:
    3
    2
    6
    8
    Output sample:
    12

For any number N, it can be divided into the product of several prime powers.

For each prime factor p to the power of N, there are p to the 0th power, p to the 1st power, p to the 2nd power, up to the d power of p, so there are d+1 divisors in total.
Therefore, there are d+1 divisors for each term P, because there are d+1 divisors from 0 to d (that is, every number has a divisor 1).
According to the law of multiplication, the number of divisors of N = (d1+1)×(d2+1)×(d3+1)×(dk+1.

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N=110,mod=1e9+7;
const int X=2*1E9+10;
int k;
int res=1;
int main()
{ map<int,int> hash;
    int n;
    cin>>n;
    int x;
    while(n--)
    {
        cin>>x;
        int i;
        for(i=2;i<=x/i;i++)
        {
            while (x%i== 0 )    //i is a divisor, so accumulate the power of i
                    {
                        x/=i;  
                         hash[i]++; //Directly accumulate the number of divisors i
                    }
        }
        if (x> 1 )   //Because N can only have one divisor greater than the root N, judge whether there are other divisors
         {

               hash[x]++; 
         }
         }
    long  long   ans= 1 ;
   //auto is automatically recognized as an iterator type, no need to declare 
  //std::map<int ,int >::iterator i; 
     for ( auto i=hash.begin();i!=hash .end();i++) //traverse each value in the Map 
           ans=ans*(i->second+ 1 )%mod;   //the number of divisors is the product of the power of each prime number + 1 
               cout <<ans;
}

You may also like...

Leave a Reply

Your email address will not be published.