Soluție HackerRank pentru Order of Prime in Factorial, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și…
- Problemă: Order of Prime in Factorial
- Domeniu: Number Theory
- Limbaj: Python 3
Challenge: Order of Prime in Factorial
Subdomeniu: Number Theory (number-theory)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775450
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/order-of-prime-in-factorial/problem
Cerință
For a given prime p, define operatorname{ord}_p(k) as the multiplicity of p in k, i.e. the number of times p appears in the prime factorization of k.
For a given p (prime) and L, let F(p,L) be the number of integers n such that 1 ≤ n ≤ L and operatorname{ord}_p(n!) is divisible by p. Here n! denotes the factorial of n.
Your job is to calculate F(p,L) given p and L.
Input Format
The first line contains the number of test cases T.
Each of the next T lines contains two integers p and L separated by a space.
Output Format
For each test case, output one line containing F(p,L).
Constraints
1 ≤ T ≤ 100000
2 ≤ p ≤ 10^18
1 ≤ L ≤ 10^18
p is prime
Sample input
2
2 6
3 6
Sample Output
2
2
Explanation
Here are the first 6 factorials: 1, 2, 6, 24, 120, 720.
The multiplicities of 2 in these numbers are: 0, 1, 1, 3, 3, 4.
Exactly two of these are divisible by 2 (0 and 4), so F(2,6) = 2.
The multiplicities of 3 in these numbers are: 0, 0, 1, 1, 1, 2.
Exactly two of these are divisible by 3 (0 and 0), so F(3,6) = 2.
Cod sursă
def ok(p, L):
sum = 0
while L > 0:
sum += L % p
L //= p
return sum % p
def solve(p, L):
L1 = L // p
r = p - ok(p, L1)
if r == p:
r = 0
if r < L % p:
return L1 + 1
else:
return L1
T = int(input())
for t in range(T):
p, L = map(int, input().split())
L += 1
L1 = L // p
ans = 0
if ok(p, L1) == 0:
ans += L % p
print(ans + solve(p, L1) * p - 1)