공부 기록

오일러 피함수는 양의 정수 $n$에 대하여 $n$보다 작은 양의 정수 $m$에 대해 $gcd(n,m)=1$인 $m$의 개수를 세는 함수이다. 오일러 피함수는 다음과 같이 정의되기도 한다. $\varphi (n)=|\{m|1\leq m\leq n,gcd(n,m)=1\}|$ 오일러 피함수는 특별한 성질을 가지고 있는데 바로 곱셈적 함수라는 것이다. $gcd(a,b)=1$ 인 $a,b$에 대해 $\varphi (ab)=\varphi (a)\varphi (b)$가 성립한다는 것이다. 증명은 다음 자료를 참고했다.  https://blog.chodaeho.com/posts/2021/eulers-totient-function/ 오일러 피 함수(Euler's phi (totient) function)오일러 피 함수(..

정수론 2024. 11. 8. 19:15

이번 글에서는 에라토스테네스의 체를 이용해 소인수분해를 빠르게 하는방법을 다루고자 한다. https://www.acmicpc.net/problem/3142 이 문제를 풀던 도중 이 방법을 알게 되었다.기본적인 에라토스테네스의 체 구현보다 최적화된 구현과 함께 알게 되었다.https://velog.io/@pakuland3/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-%EC%B5%9C%EC%A0%81%ED%99%94optimized-sieve-of-eratosthenes 에라토스테네스의 체 최적화(optimized sieve of eratosthenes)보통 에라토스테네스의 체를 구현할 때면$i$ 루프( ..

정수론 2024. 9. 29. 18:06

잠깐 복습용으로 페르마의 소정리를 적는다. $p$가 소수일 때 모든 정수 $a$에 대해 $a^p\equiv a\;modp$$p$가 소수이고 $a$가 $p$의 배수가 아닐 때 $a^{p-1}\equiv 1\;\;mod\;p$   출처: https://velog.io/@junttang/BOJ-11401-%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-3-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5-C

정수론 2024. 9. 1. 19:52

모듈러 연산모듈러 연산은 어떤 수 $a$를 $0$ 아닌 수 $b$로 나누었을 때의 나머지를 구하는 연산이다. 예를 들어 $17\;mod\;5=2$이며 모듈러 연산에서는 동치 표현을 $\equiv$로 표시한다. $7\equiv 2\;mod\;5$로 표현할 수 있다. 모듈러 연산은 프로그래밍에서 $%$ 기호로 표시된다. 모듈러 덧셈 역원모듈러 덧셈 역원이란 어떤 수 $a$와 $b$에 대해 $(a+b)mod\;N=0$을 만족하는 쌍을 의미한다. $n=5$일 때 $2$의 덧셈 역원은 $5k+3$으로 나타낼 수 있다. 모듈러 곱셈 역원 모듈러 곱셈 역원이란 어떤 수 $a$에 대해 $a\cdot a^{-1}\;mod\;N=1$로 표현할 수 있으며 곱셈 역원을 $a^{-1}$로 표현한다. 곱셈 역원은 덧셈 역원과는 ..

정수론 2024. 9. 1. 18:22

정수론 | 기호 $a|b$는 $b$가 $a$로 나누어 떨어진다는 뜻이다. 더불어 $a|b$는 $a$가 $b$의 약수라는 것을 의미한다. 유클리드 호제법 유클리드 호제법은 GCD ( GreatestCommonDivisor ) 알고리즘이라고도 불리우며 어떤 두 수 $a$와 $b$의 최대공약수를 구하는 알고리즘이다. 유클리드 호제법은 재귀적으로 실행되며 과정은 다음과 같다. int gcd(int a, int b){ int c; while(b){ c=a%b; a=b; b=c; } return a;} 확장 유클리드 알고리즘을 배우기 전에는 베주 항등식을 알아두어야 한다.  베주 항등식베주 항등식이란 식 $ax+by=g$ $(a,b$는 정수$)$ $(..

정수론 2024. 9. 1. 15:48