当前位置：网站首页>[Small Coder Study Room] ABC179-C: It is a miracle that the code does not count down

[Small Coder Study Room] ABC179-C: It is a miracle that the code does not count down

2022-08-08 14:01:00 【Small yards artisan】

碎碎念

  • 说真的,When I submitted it, I felt a little nervous in my heart,However, my execution time is high1957msIt's a miracle that the code of 's code is not ranked last……

题目地址

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

题目描述

给一个正整数N,满足A \times B + C = N的(A,B,C) How many pairs of data are there？

约束条件

  • 2 \leq N \leq 10^6
  • All values ​​are integers.

输入

输入一个正整数

N

输出

The output meets the number of submissions

示例输入 1

3

示例输出 1

3

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

示例输入 2

100

示例输出 2

473

示例输入 3

1000000

示例输出 3

13969985

题解

Small Coder Problem Solving One

  • 先看执行结果
  • 再看代码
    • 从1Start enumerating how many pairs of factor pairs there are for each value,就是固定c
    • Adding the logarithms of each value is the answer
    • very violent solution,Don't study(*￣︶￣)
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;
}
原网站

版权声明
本文为[Small yards artisan]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/220/202208081351328340.html

边栏推荐

猜你喜欢

随机推荐