Perfect divisors
Practice
3.2 (5 votes)
Modular arithmetic
Combinatorics
Number theory
Prime factorization
Basics of combinatorics
Algorithms
Modular exponentiation
Math
Problem
87% Success 2308 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
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
7 votes
Tags:
CombinatoricsNumber TheoryBasics of CombinatoricsAlgorithmsModulus ArithmeticMath
Points:30
2 votes
Tags:
AlgorithmsMathCombinatoricsBasics of Combinatorics
Points:30
1 votes
Tags:
CombinatoricsMathMedium
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
Results
Custom Input
Run your code to see the output