E. Counting Arrays

Manan Singhal
Last Updated: May 11, 2022
Difficulty Level :
EASY

Introduction

We have been given two integers, x and y. We need to calculate the counting arrays F, which is considered to be a y-factorization of x. This article will calculate the counting arrays, which contain integer elements and the product of all elements satisfies the given condition.

Problem Statement

Two positive integer numbers, x and y, are given to you. If the following conditions are met, an array F is considered a y-factorization of x:

  • In F, there are y elements, all of which are integer values.
  • The product of all y elements should be equal to x.

You must count the number of y-factorizations of x that are distinct pairwise arrays if there is at least one index i(1≤ i ≤ y) such that Ai ≠ Bi, two arrays A and B are considered different. Since, the result could be pretty huge, print it modulo 109 + 7.

Input

The number of test cases to solve is specified in the first line by the integer q (1≤ 105).

Then there are q lines, each with two integers xi and yi(1≤ xi, yi106). Each of these lines represents a test case.

Output

q integers must be printed, with the i-th integer equaling the number of yi-factorizations of xi modulo 109 + 7.

Example

Input

2
6 3
4 2

 

Output

36
6

Note

Test 2: There are six y-factorizations:

  • { - 4,  - 1}
  • {1, 4}
  • {2, 2}
  • { - 1,  - 4}
  • { - 2,  - 2}
  • {4, 1}

Solution Approach

  • Initially, calculate get_primes and get_factorials once.
  • After taking input from the user we check for all the get_primes number such that the multiplication comes out to be x with y number of elements.
  • After getting one such set we permute it with total number of ways to represent y-factorizations i.e. add negative sign if possible.
  • We keep count for each permutation possible and finally return the count.

C++ implementation

/* C++ implementation of E. counting arrays */
#include <iostream>
#include <vector>

using namespace std;

/* Calculating get_primes and get_factorials once in starting in main code */
vector<int> get_primes(int n) {
    vector<char> prime;
    for (int i = 0; i != n + 1; i += 1) {
     prime.push_back(true);   
    }
    prime[1] = false;
    prime[0] = false;
    for (int i = 2; i <= n; i += 1) {
        if (prime[i]) {
            if (i * i <= n) {
                for (int j = i*i; j <= n; j += i) {
                    prime[j] = false;
                }
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i != prime.size(); i += 1) {
        if (prime[i]) {
            ans.push_back(i);
        }
    }
    return ans;
}

/* Calculating get_primes and get_factorials once in starting in main code */
vector<int> get_factorials(int n, int mod) {
    vector<int> res = {1};
    res.reserve(2e6);
    for (int i = 1; i != n + 1; ++i) {
        res.push_back((res[i - 1] * i) % mod);
    }
    return res;
}

/* All possible permutation of integers */
int binpow(int a, int n, int mod) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 1) {
        return (binpow(a, n - 1, mod) * a) % mod;
    }
    return binpow((a * a) % mod, n / 2, mod);
}

int bin_coef(int n, int k, vector<int>& factorials, vector<int>& op_factorials, int mod) {
    return (
        (
            (
                factorials[n] * op_factorials[k]
            ) % mod 
        ) * op_factorials[n - k]
    ) % mod;
}

vector<int> factorization(int n, vector<int>& primes) {
    vector<int> res;
    res.reserve(20);
    for (int i = 0; primes[i] * primes[i] <= n; i += 1) {
        if (n % primes[i] != 0) {
            continue;
        }
        int exp = 0;
        while (n % primes[i] == 0) {
            exp += 1;
            n /= primes[i];
        }
        res.push_back(exp);
    }
    if (n > 1){
        res.push_back(1);
    }
    return res;
}

/* Main function to counting arrays */
int solve(int x, int y, vector<int>& primes, vector<int>& factorials, vector<int>& op_factorials, int mod) {
    
    auto exps = factorization(x, primes);
    int ans = 1;
    
    for (int i = 0; i != exps.size(); i += 1) {
        ans *= bin_coef(
            y + exps[i] - 1, 
            exps[i], 
            factorials,
            op_factorials,
            mod
        );
        ans %= mod;
    }
    ans = (ans * binpow(2, y - 1, mod)) % mod;
    return ans;
}

/* Main Code */
signed main() {
    /* Given modulo condition to print in the question */
    const int mod = 1e9 + 7;
    auto primes = get_primes(2000);
    auto factorials = get_factorials(2000000, mod);
    vector<int> op_factorials;
    op_factorials.reserve(factorials.size());
    for (auto val : factorials) {
        op_factorials.push_back(binpow(val, mod - 2, mod));
    }

    int q;
    /* Taking number of test cases as input from user */
    cin >> q;
    /* Running while loop to run q test cases as given in E. counting arrays problem */
    while (q--) {
        int x, y;
        /* Taking x and y input as given in E. counting arrays problem */
        cin >> x >> y;
        /* Main function to counting arrays */
        int res = solve(x, y, primes, factorials, op_factorials, mod);
        cout << res << "\n";
    }
}

 

Input

2
6 3
4 2

 

Output

36
6

Complexities

Time complexity

O(x2y)
Reason: Two nested loops are required of size x. One loop of y is called in the function binpow function, so the time complexity is O(x2y)

Space complexity

O(n), where n is the given modulo in the problem statement.
Reason: We have used the push_back operation while running the binpow function so that the space complexity will be O(n).

Frequently Asked Questions

  1. In C++, what is an array?
    An array is a sort of data structure in C++ that allows you to store multiple values of the same type.
     
  2. How are arrays classified?
    Because they hold elements of the same type, arrays are categorized as homogenous data structures. In a single array, we can't have primitive data types together. On the other hand, arrays can contain unique numbers, strings, boolean values (true and false), characters, objects, and so on.
     
  3. What is the purpose of an array?
    Arrays are best for storing several values in a single variable and processing a large number of values quickly. Using the indices, we can quickly retrieve the array elements. In any programming language, arrays are the most commonly used data type.
     
  4. In C, what is array decay?
    Array decay is the loss of an array's type and dimensions. It happens when we use a pointer or a value to send an array into a function. The array receives the initial address, which is a pointer. As a result, the array's size differs from the original.
     
  5. In C++, how do you pass an array by reference?
    A whole array cannot be passed as an argument to a function in C++. You can, however, supply a pointer to an array without an index by specifying the array's name.

Key Takeaways

In this article, we have solved the E. counting arrays problem using C++ language. We hope that this question will help you understand the concept of how to create an array with a given number of elements and the product of all elements.

Attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes