DIVISORS2 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: eiandy_eahnady
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

easy

PREREQUISITES:

Prime factorization

PROBLEM:

Given an array A of length N and an integer M, find for each i the number of divisors of A_i\cdot M!.

M \leq 100 and A_i \leq 10^5 for this version.

EXPLANATION:

M! is quite large, so attempting to compute it is already impossible (using 64-bit integers), let alone trying to multiply it by A_i and count divisors of the result.

Instead, we try to compute the number of divisors in terms of the prime factorization.
Recall that for an integer X with prime factorization

X = p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}

the number of factors of X is equal to (a_1 + 1)\cdot (a_2 + 1)\cdot\ldots\cdot (a_k + 1).
This follows from any factor of X having a prime factorization that’s obtained by choosing a power between 0 and a_i for each p_i.

So, it’s possible to count the number of factors of an integer directly from its prime factorization, without actually knowing the number.
Let’s try to apply this idea to our problem by computing the prime factorization of A_i \cdot M!

First, note that the prime factorization for x\cdot y can be obtained by computing the prime factorizations of x and y independently, and then combining them (i.e. add powers of corresponding primes).
So, to compute the prime factorization of A_i\cdot M!, we can compute the prime factorizations of A_i as well as 1, 2, 3, 4, \ldots, M, and combine them all together.

Since M \leq 100, finding the prime factorization of all the numbers from 1 to 100 is quite easy. Further A_i \leq 10^5 allows us to prime factorize A_i using the naive \sqrt{A_i} algorithm and still have it be fast enough.

M doesn’t change, so prime factorizing M! once is enough. Note that the prime factorization of M! will have at most 25 primes in it (the number of primes from 1 to 100).

Now, for each i, factorize A_i in \mathcal{O}(\sqrt {A_i}) time, then combine this prime factorization with the factorization of M! (which takes at most 25 operations), and finally use this combined prime factorization to compute the number of divisors using the formula based on powers described above.

TIME COMPLEXITY:

\mathcal{O}(N\sqrt{\max A}) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 1e5 + 5,mod = 1e9 + 7;

#define int long long

int prime[M], n, m;
int b[N];
vector<int> primes;

map<int,int>mp;
int mul (int x , int y)
{
    x %= mod;
    y %= mod;
    return (x * y) % mod;
}
void sieve() {
    for (int i = 2; i < M; i++)
        prime[i] = i;
    for (int i = 2; (i * i) < M; i++) {
        for (int j = (i * i); j < M; j += i) {
            if (prime[i] == i) {
                prime[j] = i;
            }
        }
    }
}


int fastPower(int base, int power)
{
    if(!power)
        return 1;
    int half = fastPower(base,power / 2);
    int ans = mul(half,half);
    if(power & 1) ans = mul(ans,base);
    return ans;
}
int f(int x) {

    int ans = 1;
    map<int, int> mp2 = mp;
    for (int i = 2; i * i <= x; i++)
    {
        while (x % i == 0)
        {
             mp2[i]++;
             x /= i;
        }
    }
    if(x > 1) mp2[x]++;
    for (auto i: mp2)
    {
         ans = mul(ans,i.second + 1);

    }

    return ans;
}

signed main()
{
    sieve();
    cin >> n >> m;
    for (int i = 2; i <= 1e5; ++i)
    {
        if (prime[i] == i)
        {
            primes.push_back(i);
        }
    }

    for (int i = 2; i <= m; i++)
    {
        int x = i;
        for (int j = 2; j * j <= x; j++)
        {
            while (x % j == 0)
            {
                mp[j]++;
                x /= j;
            }
        }
        if(x > 1) mp[x]++;
    }
    for (int i = 0, x; i < n; i++)
    {
        cin >> x;
        b[i] = f(x);
    }
    for (int i = 0; i < n; i++)
    {
        cout << b[i] << " ";
    }
    return 0;
}
1 Like