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