【競プロ精進ログ】ABC179-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC179-C「A x B + C」です。

ポイント

まず最初に$A，$B$，$C$全てについて全探索できるかどうかを考えますが，それぞれ$10^6$も候補が考えられるため，他の方法を考えます。正の整数という条件がついていますから，もう少し候補を絞れそうです。

まず，変数を1つ減らすことを考えてみます。$N$は与えられていますから，$A\times B$が決まれば$C$は一意に定まります。ですので，本質的には$A\times B < N$となる$A$と$B$の組み合わせを探す問題に帰着します。

さて，$A\times B < N$を満たす$(A, B)$の組み合わせは，$A$を$1$から$N - 1$まで全探索すれば良さそうです。それぞれの$A$に対して，$A\times B < N$を満たす$B>0$は$\lfloor \frac{N-1}{A} \rfloor$だけ存在します。例えば，$A=3$で$N=11$のとき，$A\times B < N$を満たす$B>0$は$B=1,2,3$です。これは，$\lfloor \frac{N-1}{A} \rfloor$という式から導き出すことができます。

以上から，$A$に関する全探索のみで条件を満たす$(A, B, C)$の組み合わせの総数を計算することができます。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N;
int ans;

int main(){
  cin >> N;
  repi(i, 1, N){
    ans += (N-1) / i;
  }

  cout << ans << endl;
}