AtCoder Beginner Contest 190 D - Staircase Sequences唯一分解定理

传送门：https://atcoder.jp/contests/abc190/tasks/abc190_d

题意

给一个N，问有多少种等差数列（公差为1）的和等于N，输出个数。

思路

假设我们选择的等差数列为[a,b]，则根据题意可以得到 $\frac{(b+a)(b-a+1)}{2}=N$ $(b+a)(b-a + 1)=2N$

不管a和b的奇偶性。都可以得到(b+a)和(b-a+1)一定是一奇一偶。 所以我们只用求出2*N的奇数因子个数，用算数基本定理求。 由于是奇数，所以2的因子就不用了，所以直接求N的奇数因子个数。

注意：任何一组解都能在左边加上一正一负给抵消掉，所以最后结果*2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;

ll get_Count(ll n) {
    ll ans = 1;
    for(ll i = 2;i * i <= n; i++) {
        if(n % i == 0) {
            int a = 0;
            while(n % i == 0) {
                a++;
                n /= i;
            }
            if(i != 2)
                ans *= (a + 1);
        }
    }
    if(n > 1)  ans *= 2;
    return ans;
}

void solve() {
    ll n; cin >> n;
    cout << get_Count(n) * 2 << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/30/atcoder-beginner-contest-190-d/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！