exqt   1년 전

n이 a^i * b^j .. 이면

답이 (1+a+a^2 .. a^(i*m)) * (1+b+b^2 .. b^(i*m)) .. 여서

((a^(i*m+1)-1)/(a-1)) * ((b^(j*m+1)-1)/(b-1)) .. 를 계산하는데 <- 등비수열합

a^(i*m+1) % 1e9+7 을 먼저 계산하니 답이 안나오네요.

(A%D)/B != A/B % D 여서 그런거 같은데 다른 방법이 있나요?

exqt   1년 전

감사합니다

51번째 줄을 res *= (mypow(a,b*m+1)-1)*mypow(a-1,DIV-2); 이렇게 고쳐봤는데

여전히 예제5처럼 DIV 범위 넘어가는건 안나오는 것 같네요

제가 뭔가 잘못 이해했나요?


cubelover   1년 전

res가 10^9, (mypow(a,b*m+1)-1)*mypow(a-1,DIV-2)가 10^18까지 갈 수 있어서 이 둘을 곱하면 long long 범위를 넘어가서 그렇습니다.

(mypow(a,b*m+1)-1)*mypow(a-1,DIV-2)%DIV로 고쳐야 할 것 같네요.

댓글을 작성하려면 로그인해야 합니다.