백준 등 프로그래밍 문제에서 계산한 결과를 10^9+7로 나눈 나머지를 출력하라 지시하는 경우가 많은데, 오버플로우를 막기 위함인건 알았지만 그 값을 소수로 사용하는 이유는 오늘 처음 알았다. 그 값이 소수여야 모듈러 곱셈 역원을 구할 수 있기 때문이다. (10^7+9는 10자리인 첫 번째 소수이기 때문에 자주 사용된다고 한다.)

풀어 말하자면 실수에서 2를 나누는 것과 1/2를 곱하는 것 대신 군 안에서는 2를 나누는 대신 모듈러 했을 때의 곱셈 역원인 정수를 대신 곱해줄 수 있는데, 모듈러하는 값이 소수일 때만 곱셈 역원이 항상 존재한다.

예시: 팩토리얼, 조합 경우의 수와 같이 매우 큰 수를 계산할 때 곱셈 역원을 사용할 수 있음

C(n, k) = n! x (k!)^-1 x ((n-k)!)^-1 (mod p)

소수가 아닌 경우 아래같은 케이스가 있음 e.g. (m = 8, a = 1, b = 2) 1 / 2 mod{8}을 구할 수 없음

  • x: 2x mod 8
  • 0: 0
  • 1: 2
  • 2: 4
  • 3: 6
  • 4: 0 ... 반복

https://www.geeksforgeeks.org/dsa/modulo-1097-1000000007 https://www.quora.com/What-exactly-is-print-it-modulo-10-9-+-7-in-competitive-programming-web-sites

5

❤️

4 people reacted.

어느 한 개발자입니다.

지금까지 다루어 봤던 언어는 아래와 같습니다. MSX Basic Z80 Assembly Pascal GW-Basic C Macromedia Director Visual Basic PHP Flash Actionscript C++ Javascript

그리고 지금은, 하스켈을 비즈니스에 쓰려고 몇 년간 노력하고 있습니다. 지금 상태는, 하스켈 자체를 연구하는 게 아니라, 하스켈 (혹은 함수형 언어) 이해가 어려운 이유를 연구하는 아마추어 연구가쯤 되어버렸습니다. 하스켈 주제로 블로그를 운영 중이지만, 아직은 하스켈 프로그래머라고 자신 있게 말하진 못하고 있습니다. 가끔 이해에 도움이 될만한 측면이 보이면, 가볍게 아이디어를 여러 SNS에 올려보곤 하는데, 그다지 프로그래머에게 쓸모 있는 내용이 포함되진 않는 것 같습니다.

Game developer. Game designer. @hyaline I know that the world is filled with fear, pain, and sadness. I want to understand and empathise with your fear, pain and sadness. Korean, English. he/him. 히아입니다. 512자라니 짧아!

Hi, I'm who's behind Fedify, Hollo, BotKit, and this website, Hackers' Pub! My main account is at @hongminhee洪 民憙 (Hong Minhee).

Fedify, Hollo, BotKit, 그리고 보고 계신 이 사이트 Hackers' Pub을 만들고 있습니다. 제 메인 계정은: @hongminhee洪 民憙 (Hong Minhee).

FedifyHolloBotKit、そしてこのサイト、Hackers' Pubを作っています。私のメインアカウントは「@hongminhee洪 民憙 (Hong Minhee)」に。

😲

1 person reacted.

인간의 언어처리와 LLM의 언어처리를 서로 비교하는 전산심리언어학(Computational Psycholinguistics)을 연구했'었'습니다.

하지만 CS덕질이 더 재밌다는 걸 깨닫고선 대학원을 탈출했습니다.

요즘은 데이터 엔지니어링과 컴파일러가 재밌어요.