문제

너무 길어서 요약했다.
M개의 주사위가 있고, i번쨰 주사위가 $N_{i}$ 번째 주사위이며 모든 면에 적힌 숫자를 더한 값이 $S_{i}$일때 각 주사위에 대해 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제다.

이는 아래 방법을 따르는데,

$S_{1}/N_{1} + S_{2}/N_{2} + … + S_{M}/N_{M}$
를 계산할 때 따르는 통분 문제를 해결하기 위해 분수를 모듈러 상의 정수로 가지도록 한다.

기약 분수 $a/b = a * b^{-1}mod X$ 로 계산한다.
$b^{-1} * b = 1(modX)$

페르마의 소정리:

소수 모듈러에서
$b^{X-1} * b = 1(modX)$
가 성립하므로
$b^{X-2} = b^{-1}(modX)$

그러나 위와 같은 방식에서 서로 다른 분수를 모듈러 상 같은 정수로 저장하는 경우가 있고, 분모가 소인수X로 가지는 경우에 역원을 계산할 수 없어서 모둘러를 1,000,000,007과 같은 큰 소수로 한다.
이 방식을 최종으로 하여 문제를 푼다.

입력

첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.

다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.

출력

모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

풀이

#include <iostream>
#define MOD 1'000'000'007

using namespace std;
typedef long long ll;

ll power(ll a, ll b) {
  ll ret = 1;
  while(b) {
    if (b & 1)
      ret = ret * a % MOD;
    b /= 2;
    a = a * a % MOD;
  }
  return ret;
}

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int M;
  cin >> M;
  ll ans = 0;

  for (int i = 0; i < M; i++) {
    int n, s;
    cin >> n >> s;
    ans += (s * power(n, MOD - 2)) % MOD;
    }
  cout << ans % MOD << '\n';
  return 0;
}

문제 파일을 다운받고, 실행하면 아무것도 없는 그냥 빈 화면이 나온다.
이렇게 패킹된 것은 ida로 열어서 정적분석해도 큰 의미는 없을 것 같다,
바로 x32dbg를 켜서 파일을 올리면

위와 같은 화면. 현재 ep는 0040A04B.

이 상황에서 아래로 쭉 내려서 확인을 해 보았다. OEP는 아마 현재 주소부터 어느 지점까지 실행되다가 특정 주소로 이동하는 지점이 있을 것이다. 실행의 마지막에 점프되는 주소가 oep이지 않을까 하는 생각임.

점프문이 있는지 살펴보면서 내려봤는데,

저 마지막 점프문이 의심스럽다.
브레이크포인트 걸고 실행해주자.
실행 결과 무사히 브레이크지점까지 실행되었고, 이제 한 줄 더 실행하면

00401150으로 점프되었다.
여기가 oep일 것으로 예상
일단 생각한 로직은 oep로 가려면 현재 주소에서 어느 부분까지가 반복문이든 뭐든 실행되다가, 결국은 점프문으로 실제 oep로 점프할 거라고 생각해서 점프되는 부분을 찾았고, 그 부분이
위에 브레이크포인트 걸어준 부분입니다.

• 전처리
• 컴파일
• 어셈블
• 링킹

전처리

전처리 과정에서는 소스코드에서 주석을 제거하고, 전처리 지시문을 처리한다.(#include #define)같은 것들이 전처리 지시문이다.

컴파일

전처리를 마친 소스코드를 어셈블리 언어로 변환한다. C언어나, C++, 파이썬 등의 하이레벨 언어가 어셈블리로 변환되는 과정인데, 이의 역과정(어셈블리어를 하이레벨 스타일의 언어로 변환하는 것)은 디컴파일이라고 한다.

어셈블

컴파일된 어셈블리 코드를 바이너리 코드(기계어)로 바꾸는 과정이다. 어셈블하게 되면 기계어로 작성된 오브젝트 파일이 된다.

링킹

위의 과정까지 마쳤으면 CPU가 실행 가능한 바이너리 파일이 되는데, 링킹을 통해 여러 오브젝트 파일들을 결합하여 실행 가능한 프로그램으로 만들게 된다.