Perfect divisors
Practice
3.2 (5 votes)
Modular arithmetic
Combinatorics
Number theory
Prime factorization
Basics of combinatorics
Algorithms
Modular exponentiation
Math
Problem
87% Success 2309 Attempts 30 Points 3s Time Limit 256MB Memory 1024 KB Max Code
You are given a positive integer \(X\) and your task is to find the summation of its perfect square divisors.
\(let \ X = {x_1}^{y_1} * {x_2}^{y_2} * {x_3}^{y_3} * .... * {x_n}^{y_n}.\)
Input format
The input is given in the following format
:
\(n\)
\(x_1 \quad y_1\)
\(x_2 \quad y_2\)
\(x_3 \quad y_3\)
\(...\)
\(x_n \quad y_n\)
Output format
Print one integer denoting the summation of the perfect square divisors of \(X\) modulo \(1e9 + 7\).
Constraints
\(1 \leq x_i, y_i \leq 2\times {10^6}\)
\(1 \leq n \leq 10^5\)
Explanation
the sampe input corresponds to X = 2^2 * 3^1 = 12, which has these divisors : 1, 2, 3, 4, 6, 12.
Among these divisors these are pefect square : 1, 4, so the answer is 1 + 4 = 5
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
1 votes
Tags:
CombinatoricsMathMedium
Points:30
18 votes
Tags:
CombinatoricsMathMedium
Points:30
4 votes
Tags:
CombinatoricsMathMediumNumber Theory
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor