최대공약수의 약수는 모든 수들의 공약수이고 최소공배수의 배수는 모든 수들의 배수이다

1. 문제

 

1565번: 수학 (acmicpc.net)

1565번: 수학

 

2. 풀이

 

수들의 최소공배수의 배수는, 모든 수들의 공배수이며,

 

수들의 최대공약수의 약수는, 모든 수들의 공약수이다.

 

M에서 최대공약수를 구한 다음에, 최대공약수의 약수들을 구한다.

 

$O(\sqrt{N})$으로 구할 수 있다.

 

여기서 set()을 이용해서 중복을 피해준다

 

다음 D에서 최소공배수를 구해준다.

 

a,b의 최소공배수는 a*b/gcd(a,b)로 구할 수 있

 

그리고 M에서 구한 약수들이 최소공배수의 배수인지 판단해준다

 

from sys import stdin

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

def lcm(a,b):
    
    return a*b//gcd(a,b)

d,m = map(int,stdin.readline().split())

D = list(map(int,stdin.readline().split()))

M = list(map(int,stdin.readline().split()))

#M에서 최대공약수를 구한다
gcd_m = M[0]

for i in range(1,m):
    
    gcd_m = gcd(gcd_m,M[i])

#최대공약수의 약수는, M의 모든 수들의 공약수이다.
divisor = set()

for i in range(1,int(gcd_m**(1/2))+1):
    
    if gcd_m % i == 0:
        
        divisor.add(i)
        divisor.add(gcd_m//i)

#D에서 최소공배수를 구한다
lcm_d = D[0]

for i in range(1,d):
    
    lcm_d = lcm(lcm_d,D[i])

#약수들이 최소공배수의 배수라면, 
#D의 모든 수들의 배수이면서 M의 모든 수들의 약수가 된다
count = 0

for div in divisor:

    if div % lcm_d == 0:
        
        count += 1
        
print(count)