오일러 함수의 성질과 계산 방법
오일러 함수 φ(n)은 1부터 n까지 n과 서로 소인 수의 개수를 나타냅니다. 두 수 a와 b가 서로 소일 때 gcd(a,b)=1이 성립합니다.
재귀적 계산식
임의의 양의 정수 a에 대해 다음 식이 성립합니다:
φ(ab) = φ(a)×φ(b)×gcd(a,b)/φ(gcd(a,b))
a와 b가 서로 소일 경우 φ(ab) = φ(a)×φ(b)가 됩니다.
증명
n을 소인수 분해한 후 φ(n)을 계산하는 방식을 통해 증명할 수 있습니 ...
7월 11일 23:00에 게시됨
빠른 거듭제양 및 수론 알고리즘
빠른 거듭제곱
비트 시프트를 사용한 거듭제곱은 O(1)의 시간 복잡도를 가지지만 최대 63 제곱까지만 가능합니다. 반면, 빠른 거듭제곱 알고리즘은 O(log n)의 시간 볔잡도를 가지며 10^9 제곱까지 지원합니다. 모듈러 연산은 곱셈 단계에서 수행해야 합니다.
이 방법은 a^k mod p를 계산하는 데 사용되며, a, k, p는 각각 1e9까지 가능합니다. 이를 통해 O(log k)의 시간 ...
7월 11일 16:29에 게시됨
수론의 기초 개념과 응용
수론은 정수의 성질을 연구하는 수학의 핵심 분야로, 특히 약수와 배수, 소수, 합동식 등에 관한 깊이 있는 분석을 포함한다. 본 문서에서는 수론에서 중요한 몇 가지 개념과 그 활용 방법을 다룬다.
곱셈 함수
정의역이 양의 정수 집합인 함수 ( f )가 임의의 서로소인 두 자연수 ( p, q )에 대해 ( f(pq) = f(p)f(q) )를 만족하면, 이 함수를 곱셈 함수(multiplicative f ...
6월 29일 01:41에 게시됨
수론의 고급 알고리즘
BSGS
이산 로그 문제를 해결하기 위한 알고리즘으로, 주어진 a, b, p에 대해 a^n ≡ b (mod p)를 만족하는 최소의 양의 정수 n을 찾는 데 사용됩니다.
알고리즘 절차
이 문제는 두 가지 경우로 나눌 수 있습니다:
일반 BSGS
a와 p가 서로소(a⊥p)인 경우입니다.
이 경우 a는 역원을 가지며, BSGS는 이 성질을 이용해 제곱근 시간 알고리즘을 설계합니다.
a^n의 주기 길이는 φ ...
6월 22일 23:02에 게시됨
이항 원리와 비트 마스크를 활용한 포함-배제 원리 구현
포함-배제 원리의 기초 개념
포함-배제 원리는 여러 집합의 합집합 크기를 정확히 계산하기 위한 수학적 방법이다. 단순히 각 집합의 원소 수를 더하면 중복이 발생하므로, 이를 체계적으로 보정하여 중복 없이 전체 개수를 구한다.
예를 들어 세 개의 집합 \( A, B, C \)가 있을 때, 그들의 합집합의 크기는 다음과 같이 표현된다:
\[
|A \cup B \cup C| = |A| + |B| + | ...
6월 22일 01:38에 게시됨
조합론과 수론의 주요 개념들
조합론과 수론은 알고리즘 문제 해결에서 중요한 역할을 한다. 여기에서는 이 분야의 핵심적인 개념들과 이를 활용한 몇 가지 기법들을 다룬다.
조합론
가법 원리와 곱셈 원리
가법 원리에 따르면, 어떤 일을 수행하는 두 가지 방법이 있을 때 첫 번째 방법으로는 a개의 방법이 있고, 두 번째 방법으로는 b개의 방법이 있다면 총 a+b개의 방법으로 일을 완수할 수 있다. 곱 ...
6월 20일 17:51에 게시됨
동일 방정식과 확장 유클리드 알고리즘
x와 y의 최대공약수가 d일 때
(x,y)=d
방정식으로 변환하면
ax+by=d
매개변수 x와 y에 대한 표현식 x y의 부호는 상관없음
x=x0+kb/d (반대쪽을 더함)
y=y0-ka/d
//확장 유클리드 알고리즘
int extended_gcd(int a, int b, int &x, int &y)//ax=d%(mod b) x와 y는 ax+by=d 방정식의 한 해 반환값은 최대공약수(마지막 레이어의 a)
{
if (!b)
{
x ...
6월 6일 21:47에 게시됨
약수 관련: 약수의 개수
N = (p1c1) * (p2c2) * ... * (pk^ck) 형태로 표현될 때
N2 = (p1(c12)) * (p2^ (c22)) * ... * (pk^ (ck*2)) 형태가 됩니다.
약수의 개수 f[N] = (c1+1)(c2+1)...(ck+1)
배수를 이용한 약수 개수 구하기
이 문제에서는 공식을 사용하지 않고, 약수를 구하는 대신 배수를 이용해 해결합니다.
#include <cstdio>
#include <cstring>
#include <iostream>
...
6월 2일 20:24에 게시됨