long long 자료형의 mod 연산 비용

  • Neon
    Neon

    SRM 554를 연습하다가 멘붕해서 남깁니다.

    #include <iostream>
#include <cstdlib>

using namespace std;

long long mod = 1200000000LL;
long long mod2 = mod * mod;

int main(void) {
    long long ret = 0;
    for(int i=0;i<100000000;i++) {
        int tmp1 = rand() % mod;
        int tmp2 = rand() % mod;
        ret += (long long)tmp1 * tmp2;
        ret %= mod;
    }
    cout << ret << endl;
}

    이거랑

    #include <iostream>
#include <cstdlib>

using namespace std;

long long mod = 1200000000LL;
long long mod2 = mod * mod;

int main(void) {
    long long ret = 0;
    for(int i=0;i<100000000;i++) {
        int tmp1 = rand() % mod;
        int tmp2 = rand() % mod;
        ret += (long long)tmp1 * tmp2;
        if(ret >= mod2) ret -= mod2;
    }
    ret %= mod;
    cout << ret << endl;
}

    이거의 속도를 비교해보면(srand를 쓰지 않았으니 결과는 두 코드 모두 동일)
    1번 타자 : 4.996s
    2번 타자 : 3.645s

    실제 SRM 연습에선 이 차이가 더 극명하게 나와서, 위 방법으로 matrix multiplication을 하면 2초 TLE가 나던 코드가, 아래 방법으로 최적화를 거치니까 0.5초로 결과가 나오더라능...

    생각보다 mod 연산의 비용이 엄청 크다는 걸 알았습니다 OTL


    11년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.