[AtCoder] ABC 179 C – A x B + C

2020年9月20日2020年12月13日

問題

方針

\( A, B \) を全探索

\( A, B \) を全探索します。\( A \) を固定した時、\( A \times b \geq N \) となるような \( b \) より大きいものを探索する必要はありません。

\( A\) を全探索

\( A \) を固定した時、

\[ B = \dfrac{N – C}{A}\]

となるので、このとき、\( B \) の最大値は \( C = 1 \)のときなので、最大値は

\[ \left \lfloor \dfrac{N-1}{A} \right \rfloor\]

となります。したがって、

\[ \sum_{a = 1}^{N} \left \lfloor \dfrac{N-1}{a} \right \rfloor\]

を求めます。

コード

\( A, B \) を全探索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll cnt = 0;
    for (int a = 1; a <= N; a++) {
        for (int b = 1; b <= N; b++) {
            if (a * b >= N) break;
            cnt++;
        }
    }
    cout << cnt << "\n";
    return 0;
}

\( A\) を全探索

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll cnt = 0;
    for (int a = 1; a <= N; a++) {
        cnt += (N - 1) / a;
    }
    cout << cnt << "\n";
    return 0;
}