유미의 기록들

📌문제  📝 풀이과정단순히 for문을 이용해서 A를 B번 곱한 다음, 나머지를 출력하면 될까?문제를 볼 때 가장 먼저 입력의 최대, 최소 범위를 봐야 한다여기서 최대 범위는 20억인데, for문으로 A를 B번 곱하게 되면 즉 시간 복잡도는 20억이 된다 그렇다면 어떻게 접근해야 할까?'모듈러 연산'과 '지수법칙'으로 접근하면 된다 모듈러 연산 모듈러 식을 연산자를 이용하여 표현해보면  → 문제에서 최대범위로 계산 했을 때 A(20억)을 B(20억) 번 계산해야 한다 그렇게 되면 long long의 범위를 벗어나고 오버플로가 발생하게 된다 따라서 A를 C로 나누면서 곱하는 식으로 계산해야 한다    지수법칙 2를 8번 곱하면 연산 횟수가 많다따라서 지수법칙에 따라 2^4를 하나의 변수 K에 넣고  K ..