当前位置：网站首页>【小码匠自习室】ABC179-C：代码竟然没排倒数堪称一大奇迹

【小码匠自习室】ABC179-C：代码竟然没排倒数堪称一大奇迹

2022-08-08 13:53:00 【小码匠】

碎碎念

说真的，我在提交时内心那叫一个忐忑，不过我执行用时高达1957ms的代码竟然没排倒数堪称一大奇迹……

题目地址

C - A x B + C
- https://atcoder.jp/contests/abc179/tasks/abc179_c

题目描述

给一个正整数N，满足A \times B + C = N的(A,B,C) 数据对个数有多少？

约束条件

2 \leq N \leq 10^6
所有值都是整数.

输入

输入一个正整数

输出

输出满足提交个数

示例输入 1

示例输出 1

满足条件的 A \timesB + C = 3: (A, B, C) = (1, 1, 2), (1, 2, 1), (2, 1, 1).

示例输入 2

示例输出 2

示例输入 3

示例输出 3

13969985

题解

小码匠题解一

先看执行结果

再看代码
- 从1开始枚举每一个值的因数对有多少对，就是固定c
- 将每个值的对数相加即为答案
- 很暴力的解法，大家不要学哦(*￣︶￣)

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i < n; ++i) {
        for(int j = 1; j * j <= i; ++j) {
            if (i % j == 0) {
                if (i / j == j) {
                    ans++;
                } else {
                    ans += 2;
                }
            }
        }
    }
    cout << ans;
}

参考题解

思路：固定a，枚举b的可能性，c随b变化，-1是因为要保证c至少为1

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

int main() {
    long long N;
    cin >> N;
    long long res = 0;
    for (long long a = 1; a < N; ++a) res += (N - 1)/ a;
    cout << res << endl;
}

参考题解2

思路：暂时没看懂

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

int main() {
    long long N;
    cin >> N;
    long long res = 0;
    for (long long A = 1; A * A < N; ++A) ++res;
    for (long long A = 1; A * A < N; ++A) {
        long long num = max((N - 1) / A - A, 0LL);
        res += num * 2;
    }
    cout << res << endl;
}

原网站

版权声明
本文为[小码匠]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2068165