Tag: number theory

from collections import Counter, defaultdict

input = sys.stdin.readline
print = sys.stdout.write

N = int(input())

students = [int(input()) for _ in range(N)]
MAX_STUDENT = max(students) + 1

counter = Counter(students)
toktok = defaultdict(int)

for i in range(1, MAX_STUDENT):
    for j in range(i, MAX_STUDENT, i):
        if j in counter:
            toktok[j] += counter[i]

print("\n".join(str(toktok[s] - 1) for s in students) + "\n")

ring = list(map(int, input().split()))
first = ring[0]
rings = ring[1:]
def gcd(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

for r in rings:
    if first % r == 0:
        print(f"{first // r}/1")
    elif r % first == 0:
        print(f"1/{r // first}")
    else:
        g = gcd(first, r)
        print(f"{first // g}/{r // g}")

$a, b \in \mathbb{Z}$이고 $a$를 $b$로 나눈 나머지를 $r$이라 하자. ($b \leq a, 0 \leq r \leq b$)

$a, b$의 최대 공약수를 $(a, b)$라고 하면, 다음이 성립한다.

$(a, b)=(b, r)$

출처: wikipidia

$r$이 0이 될 때 알고리즘을 멈추며, 이 때의 $b$가 최대공약수가 된다.

예를 들어 1460과 1037에 대해 알고리즘을 진행해보면 다음과 같다.

$r$이 0일때 $b$가 4이므로 1460과 1037의 최대공약수는 4이다.

div = list(map(int, input().split()))
min, max = float('inf'), float('-inf')
for d in div:
    if min > d : min = d
    if max < d : max = d
print(min * max)

nums = str(sys.stdin.readline().strip())
if '0' not in nums:
    print(-1)
else:
    l = [0] * (int(max(nums)) + 1)
    s = ''
    sum = 0
    for i in nums:
        l[int(i)] += 1
    for i in range(len(l)-1, 0, -1):
        s += str(i) * l[i]
        sum += i * l[i]
    if sum % 3 == 0: print(int(s) * (10 ** l[0]))
    else: print(-1)