問題#

問題ページへのリンクはこちら

考え方#

A, BをX、C, DをYとおく。X + Y = Nと考える。すると、Y = N - Xより、(1, N-1), (2, N-2), ⋯ , (N-1, 1)の組み合わせができる。XとYの約数の個数はそれぞれ独立なので、f(X, Y) = f(X) * f(Y)となる。つまり、XとYの約数をかけた結果を足し合わせていけば求められる。
※この問題では、制約により全探索ができない。

コード#

#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)
#define ALL(a) (a).begin(),(a).end()


int main() {
  int N, count = 0, total = 0;
  cin >> N;
  vector<int> divisor_num_array;

  for (int i = 1; i < N; i++) {
    // cout << "X = " << i << endl;
    // 約数を求める処理（こっちの方が早い）
    for (int j = 1; j * j <= i; j++) {
      if (i % j == 0) { 
        int k = i / j;
        if (j == k) {
          count++;
          // cout << j << "\n";
        } else {
          count = count + 2;
          // cout << j << "\n";
          // cout << k << "\n";
        }
      }
    }
    /*
    // これでも約数を求められる
    for (int i = 1; i <= a; i++) {
      if (a % i == 0) cout << i << "\n";
    }
    */
    divisor_num_array.emplace_back(count);
    // cout << "count = " << count << endl;
    count = 0;
  }
  REP(i, N-1) {
    // cout << "divisor_num_array[" << i << "] : " << divisor_num_array[i] << endl;
  }
  // cout << "---" << endl;
  REP(i, N-1) {
    total = total + divisor_num_array[i] * divisor_num_array[N - 2 - i];
    // cout << "divisor_num_array[" << i << "] : " << divisor_num_array[i] << endl;
    // cout << "divisor_num_array["<< N - 2 - i << "] : " << divisor_num_array[N - 2 - i] << endl;
    // cout << "total : " << total << endl;
  }
  cout << total << endl;
  
}