Soluție HackerRank pentru Manasa and Calculations, subdomeniul Algebra, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Manasa and Calculations
- Domeniu: Algebra
- Limbaj: Python 3
Challenge: Manasa and Calculations
Subdomeniu: Algebra (algebra)
Scor cont: 60.0 / 60
Submission status: Accepted
Submission score: 1.0
Submission ID: 464745004
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/manasa-and-calculations/problem
Cerință
Manasa is a student in the department of Mathematics. She is pretty good at doing calculations involving small numbers, but large numbers scare her. So she wants you to help her in the following calculations.
Given two numbers in the following manner:
A = p_1 ^a_1 × p_2 ^a_2 × p_3 ^a_3 × ·s × p_N ^a_N
B = p_1 ^b_1 × p_2 ^b_2 × p_3 ^b_3 × ·s × p_N ^b_N
(p_i is a prime number, and all the p_i's are distinct)
She wants you to calculate S for her, where S is the sum of m+n for all pairs of numbers where m ≤ n, gcd(m,n) = B and text{lcm}(m,n) = A. In other words:
S = ∑_{substack{gcd(m,n)=B text{lcm}(m,n) = A m≤ n}} (m+n)
As the value of S can be very large, she wants you to print S bmod 10^9+7.
Input Format
The first line contains an integer N, the number of prime factors.
Each of the next N lines contains three numbers: p_i, b_i and a_i.
Output Format
Print the value of S bmod 10^9+7.
Constraints
1≤ N ≤ 500
2≤ p_i ≤ 5000
1≤ a_i ≤ 10^9
1≤ b_i ≤ 10^9
b_i ≤ a_i
Sample Input
2
2 1 2
3 1 2
Sample Output
72
Explanation
We have B = 6 and A = 36. There are two pairs of integers (m,n) with gcd equal to 6 and text{lcm} equal to 36, and such that m ≤ n. These are (12,18) and (6,36):
- gcd(12,18) = 6 and text{lcm}(12,18) = 36
- gcd(6,36) = 6 and text{lcm}(6,36) = 36
Hence, S = (12+18)+(6+36) = 72
Cod sursă
# Enter your code here. Read input from STDIN. Print output to STDOUT
from functools import reduce
m = 1000000007
def mul_m(a, b):
return a * b % m
def zpow(a, b, m):
return 0 if b == 0 else pow(a, b, m)
n = int(input())
a = [0] * n
b = [0] * n
p = [0] * n
for i in range(n):
p[i], b[i], a[i] = map(int, input().split())
B = reduce(mul_m, [pow(p[i], b[i], m) for i in range(n)])
if all(a[i] == b[i] for i in range(n)):
print(B * 2 % m)
else:
print(B * reduce(mul_m, [1 + zpow(p[i], a[i] - b[i], m) for i in range(n)]) % m)