du熊的机器人

#include <cstdio>

#include <vector>

#include <utility>

#include <algorithm>

 

using namespace std;

 

typedef long long llint;

 

const int MAXN = 2012;

 

const llint BASE = 1000000000;

vector<pair<int, int> > factor[MAXN];

 

void init() {

  for (int i = 1; i < MAXN; ++i) {

    int t = i;

    for (int j = 2; j * j <= t; ++j) {

      int k = 0;

      while (t % j == 0) {

        t /= j;

        ++k;

      }

      if (k > 0) {

        factor.push_back(make_pair(j, k));

      }

    }

    if (t > 1) {

      factor.push_back(make_pair(t, 1));

    }

  }

}

 

void add(int r[MAXN], int k, const vector<pair<int, int> >& v) {

  for (int i = 0; i < (int)v.size(); ++i) {

    r[v.first] += k * v.second;

  }

}

 

int r[MAXN];

vector<llint> ans;

 

int main() {

  int re, n, m;

  llint t;

  vector<llint> v;

 

  init();

  scanf("%d", &re);

  for (int ri = 1; ri <= re; ++ri) {

    scanf("%d%d", &n, &m);

    if (n > m) {

      swap(n, m);

    }

    --m;

 

    fill(r, r + MAXN, 0);

    r[2] = 1;

    add(r, 1, factor[n]);

    for (int i = 1; i < m; ++i) {

      add(r, 2, factor[n + i]);

    }

    if (m > 0) {

      add(r, 1, factor[n + m]);

    }

    for (int i = 1; i <= m; ++i) {

      add(r, -2, factor);

    }

    add(r, -1, factor[m + 1]);

 

    t = 1;

    v.clear();

    for (int i = 0; i < MAXN; ++i) {

      for (int j = 0; j < r; ++j) {

        if (t * i < BASE) {

          t *= i;

        } else {

          v.push_back(t);

          t = i;

        }

      }

    }

    if (t > 1) {

      v.push_back(t);

    }

 

    ans = vector<llint>(1, 1);

    for (int i = 0; i < (int)v.size(); ++i) {

      t = 0;

      for (int j = 0; j < (int)ans.size(); ++j) {

        t += ans[j] * v;

        ans[j] = t % BASE;

        t /= BASE;

      }

      while (t > 0) {

        ans.push_back(t % BASE);

        t /= BASE;

      }

    }

    printf("%lld", ans.back());

    for (int j = (int)ans.size() - 2; j >= 0; --j) {

      printf("%09lld", ans[j]);

    }

    puts("");

  }

 

  return 0;

}