수학

• 정수론 (소수, 약수의 관계), 기하학 이 대표적
• 기하는 피타고라스의 정리를 활용한 점 사이의 거리, 삼각형의 넓이 (EASY) 부터 CCW (점 3개가 ccw 인지 cw 인지 회전 방향), 컨벡스헐, 좌표기하 (HARD: 코테는 잘 안나오고 대회에 나옴) 등 난이도 격차가 큼

정수론

gcd / lcd

• 유클리드 호제법 (Euclidean algorithm) 활용
• GCD(a,b) = GCD(b, a%b)
  • 방법 1

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

  • 방법 2

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

  • 방법3

    import math
    math.gcd(a,b)
    

    • 속도: 방법3 (fastest) > 방법2 > 방법1
• LCM(a,b) = (a x b)/GCD(a,b)

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

• 파이썬 아닌경우 a / gcd(a,b) * b 순서로 계산 (int overflow 방지)

소수체크와 소인수분해

• 소수체크: 반복문 O(sqrt(N))

    def isPrime(N):
    for i in range(2, N):
        if N%i == 0: return False
        if i*i > N: break
    return True
  

• 소인수분해: 트릭! O(sqrt(N))

    def prime_factorization(N):
    p, fac = 2, []
    while p**2 <= N:
        if N%p == 0:
        N //= p
        fac.append(p)
        else:
        p += 1
    if N > 1: fac.append(N) # 너무 커서 탈출한경우 이거 자체가 prime
    return fac
  

에라스토스테네스의 채 활용한 소수

• 에라스토스테네스의 채
  • 소수 리스트 생성: 가장 빠르고 가장 효율적
  • 원리: 앞에서부터 배수 전부 삭제
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    2 3 5 7 9 11 13 15
    3 5 7 11 13

    def era_prime(N):
        ck, ret = [0 for _ in range(N+1)], []
        for i in range(2, N):
            if ck[i] == 0 : ret.append(i)
            else: continue
            for j in range(i**2, N, i): ck[j] = 1
        return ret
    

• 소인수 분해 (소수 리스트 크기는 sqrt(N) 보다 커야함)

    def prime_factorization_2(N                 , p):
    fac = []
    for i in p:
    if N == 1 or N > i*i : break
    while N%i == 0:
        fac.append(i)
        N //= i
    return fac
  

• 소인수의 개수

    def era_factor_count(N):
    A = [0 for _ in range(N+1)]
    for i in range(2, N):
        for j in range(i, N, i):
        A[j] += 1
    return A
  

• 소인수의 합

    def era_factor_sum(N):
    A = [0 for _ in range(N+1)]
    for i in range(2, N):
        for j in range(i, N, i):
        A[j] += i
    return A
  

• 소인수분해를 위한 또하나의 트릭

    def era_factorization(N):
    A = [0 for _ in range(N+1)]
    for i in range(2, N):
        if A[i]: continue
        for j in range(i, N, i):
        A[j] = i
    return A
    # 소인수 분해
    A = era_factorization(100)
    N = 84
    while A[N] != 0:
        print(A[N])
        N //= A[N]
  

거듭제곱 연산 (C++, Java 유저는 무적권 알아야함. 파이썬은 상관 x)

$a ^ {11} = a ^ 1 * a ^ 2 * a ^ 8$ 을 이용

def pow_adv(a, b, mod):
    ret = 1
    while b > 0:
      if b % 2: ret = ret*a%mod
      a, b = a*a%mod, b//2
    return ret

pow(a, b, 1000000007)

pow 가 압도적으로 빠름 !