[ Baekjoon - 단계별로 풀어보기(06/11~06/13) ] - 14단계 : 정수론 및 조합론

• 5086 : 배수와 약수

while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    print("factor" if b%a==0 else ("multiple" if a%b==0 else "neither"))

 

• 1037 : 약수

n=int(input())
l=list(map(int,input().split()))
l.sort()
print(l[0]*l[-1])

 

• 2609 : 최대공약수와 최소공배수

l=list(map(int,input().split()))
lcf=1;ok=0
minVal=min(l)
for i in range(2,minVal+1):
    while True:
        if l[0]%i==0 and l[1]%i==0:
            lcf*=i
            l[0]//=i
            l[1]//=i
        else:
            break
print(lcf)
print(lcf*l[0]*l[1])

 

• 1934 : 최소공배수

for i in range(int(input())):
    h,s=map(int,input().split())
    a,b=h,s

    if(a>b) : a,b = b,a
    while(b!=0):
        a=a%b
        a,b=b,a

    print(a*(h//a)*(s//a))

 

• 29981 : 검문

import math
import sys
input=sys.stdin.readline

t=int(input())
s = []
a = []
gcd = 0
for i in range(t):
    s.append(int(input()))
    if i == 1:
        gcd = abs(s[1] - s[0])
    gcd = math.gcd(abs(s[i] - s[i - 1]), gcd)
gcd_a = int(gcd ** 0.5)
for i in range(2, gcd_a + 1):
    if gcd % i == 0:
        a.append(i)
        a.append(gcd // i)
a.append(gcd)
a = list(set(a))
a.sort()
for i in a:
    print(i, end = ' ')

 

• 3036 : 링

import math
n=int(input())
l=list(map(int,input().split()))[:n]
for i in l[1:]:
    v=math.gcd(l[0],i)
    print(l[0]//v,end="/")
    print(i//v)

 

• 11050 : 이항 계수 1

n,k=map(int,input().split())
N,K=1,1
k=n-k if n//2<k else k
for i in range(n,n-k,-1):
    N*=i
    K*=(k-n+i)
print(N//K)

 

• 11051 : 이항 계수 2

import sys
input=sys.stdin.readline

n,k=map(int,input().split())
N,K=1,1
k=n-k if n//2<k else k
for i in range(n,n-k,-1):
    N*=i
    K*=(k-n+i)
print((N//K)%10007)

 

• 1010 : 다리 놓기

for i in range(int(input())):
    k,n=map(int,input().split())
    N,K=1,1
    k=n-k if n//2<k else k
    for i in range(n,n-k,-1):
        N*=i
        K*=(k-n+i)
    print(N//K)

 

• 9375 : 패션왕 신해빈

t=int(input())
for i in range(t):
    category=[];dressCnt=[]
    for j in range(int(input())):
        a,b=input().split()
        ok=0;idx=0
        for k in range(len(category)):
            if category[k]==b:
                ok=1
                idx=k
                break
        if ok==0:
            category.append(b);dressCnt.append(1)
        else:
            dressCnt[k]+=1
    answer = 1
    for c in dressCnt:
        answer *= (c+1) 
    print(answer-1)

 

• 1676 : 팩토리얼 0의 개수

n=int(input())
res=1
for i in range(n,1,-1):
    res*=i
l=list(str(res))
cnt=0
for i in range(len(l)-1,0,-1):
    if l[i]!="0":
        break
    else:
        cnt+=1
print(cnt)

 

• 2004 : 조합 0의 개수

def funCnt(n,k):
    cnt=0
    while k!=0:
        k//=n
        cnt+=k
    return cnt

import sys
input=sys.stdin.readline
n,m=map(int,input().split())

if m == 0:
    print(0)  
else:       
    print(min(funCnt(2,n)-funCnt(2,m)-funCnt(2,n-m), funCnt(5,n)-funCnt(5,m)-funCnt(5,n-m)))