글 읽기 - (n(n+1)/2) mod k를 오버플로우 없이 계산할 수 있나요?

chatterboy 8년 전 0

n <= 10¹⁸, k <= 10⁶일 때

오버플로우 없이 계산이 가능한가요??

august14 8년 전 0

네

chatterboy 8년 전 0

아하! 가능하네요.

koosaga 8년 전 1

k가 10^18 이어도 가능합니다.

typedef long long lint;

lint mul(lint x, lint y){ // returns (x * y) % k w/o overflow problem.
    lint ret = 0;
    while(x){
        if(x&1) ret += y;
        y <<= 1, x >>= 1;
        y %= k, ret %= k;
    }
    return ret;
}

chatterboy 8년 전 1

@koosaga

코드까지 알려주시고..

감사합니다 ~

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

문제

문제

출처

ICPC

(n(n+1)/2) mod k를 오버플로우 없이 계산할 수 있나요?

chatterboy 8년 전 0

august14 8년 전 0

chatterboy 8년 전 0

koosaga 8년 전 1

chatterboy 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말