모듈러2 백준 1629/c++ )) 곱셈 - divde and conquer, 재귀함수 그대로 주는대로 계산하면 연산시간이 너무 길어서 시간 초과하는 문제이다 재귀 함수로 분할정복 divde and conquer를 사용하여 연산 수를 줄이고, 각 입력의 최대값이 int 의 최대치 값 이므로 long long 을 사용하여 결과값의 오버플로우를 1차로 막는다 분할한 값을 합칠때 큰 수끼리의 곱셈을 해야하므로 long long 뿐 아니라 %c 로 모듈러 연산을 해줘서 2차로 오버플로우를 막아야 하는 문제이다 재귀함수라지만 내가 gr로 작성한 부분이 gr=gr*gr 이고 gr=gr*a%c 이라는 부분에서 왜인지 이해하느라 머리가 터졌고 시간도 몇시간을 걸려서 이해했지만, 이해했으니 비슷한 유형도 이제 익숙해질것이다 내일을 공부를 위해 더 늦기전에 자자... #include using namespa.. 2022. 6. 17. 모듈러 연산 모듈은 %연산에서 나누는 수를 말한다 c = a%b // a를 b로 나누고 남은 나머지가 c이다 c = a mod b // b 를 모듈이라 한다 모듈러 연산은 % 를 사용하여 남은 나머지를 연산하는 것을 말한다 외워두면 몇가지 공식이 있어서 아래에 정리한다 a ≡ b mod n 이고 b ≡ c mod n 이면 a ≡ c mod n [ ( a mod n) + (b mod n) ] mod n = (a + b) mod n [ ( a mod n) - (b mod n) ] mod n = (a - b) mod n [ ( a mod n) * (b mod n) ] mod n = (a * b) mod n 2022. 6. 10. 이전 1 다음
