Soluție HackerRank pentru Easy GCD, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Easy GCD
- Domeniu: Number Theory
- Limbaj: Python 3
Challenge: Easy GCD
Subdomeniu: Number Theory (number-theory)
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464725176
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/easy-gcd-1/problem
Cerință
We call a sequence of n non-negative integers, A, *awesome* if there exists some positive integer x gt 1 such that each element a_i in A (where 0 ≤ i lt n) is *evenly divisible* by x. Recall that a evenly divides b if there exists some integer c such that b = a · c.
Given an awesome sequence, A, and a positive integer, k, find and print the maximum integer, l, satisfying the following conditions:
1. 0 ≤ l ≤ k
2. A cup {l} is also awesome.
Input Format
The first line contains two space-separated positive integers, n (the length of sequence A) and k (the upper bound on answer l), respectively.
The second line contains n space-separated positive integers describing the respective elements in sequence A (i.e., a_0, a_1, …, a_n-1).
Output Format
Print a single, non-negative integer denoting the value of l (i.e., the maximum integer ≤ k such that A cup {l} is awesome). As 0 is evenly divisible by any x gt 1, the answer will always exist.
Sample Input 0
3 5
2 6 4
Sample Output 0
4
Explanation 0
The only common positive divisor of 2, 6, and 4 that is gt 1 is 2, and we need to find l such that 0 ≤ l ≤ 5. We know l ne 5 because x=2 would not evenly divide 5. When we look at the next possible value, l = 4, we find that this is valid because it's evenly divisible by our x value. Thus, we print 4.
Sample Input 1
1 5
7
Sample Output 1
0
Explanation 1
Being prime, 7 is the only possible value of x gt 1. The only possible l such that 0 ≤ l ≤ 5 is 0 (recall that (0 / 7) = 0), so we print 0 as our answer.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ 10^9
- 1 ≤ a_i ≤ 10^9
Cod sursă
#!/bin/python3
import math
import os
import random
import re
import sys
from collections import defaultdict
def factors(n):
res=defaultdict(int)
while n&1!=1:
res[2]+=1
n//=2
for i in range(3,int(pow(n,0.5))+1,2):
while n%i==0:
res[i]+=1
n//=i
if n>2:
res[n]+=1
return res
if __name__ == '__main__':
nk = input().split()
n = int(nk[0])
k = int(nk[1])
A = list(map(int, input().rstrip().split()))
hcf=A[0]
for i in range(1,n):
hcf=math.gcd(hcf,A[i])
factor=factors(hcf).keys()
M=0
for x in factor:
M=max(M,k-k%x)
print(M)