当前位置：网站首页>乐山师范程序设计大赛2020- H: 最小公倍数【求因子个数】

乐山师范程序设计大赛2020- H: 最小公倍数【求因子个数】

2022-07-19 05:15:00 【星空皓月】

题目描述

给定一个整数 b，另外 a 表示 1 到 1018 中的所有整数，计算式子 [a, b] / a 有多少个不同的结果，这里 [a, b] 表示整数 a 与整数 b 的最小公倍数。

输入

输入只包含一组数据；
第一行包含一个整数 b （1 ≤ b ≤ 1010）。

输出

输出式子不同结果的数量。

样例输入

样例输出

提示

任意正整数 a 与 2 的最小公倍数必定等于 2 * a 或者 a，故式子 [a, b] / a 的结果只能是 1 或者 2。

思路

多枚举几个b，我们会发现就是去求b的因子个数。
例如b = 4；
(4, a) == >最小公倍数可能为(a，2a，4a)，再除以a就为(1,2,4),观察发现这些都是4的因子。
所以直接求因子的个数有多少个，但是b的范围很大，再次观察[1，sqrt(b)]中存在这个n的一半因子，(sqrt(b),n)存在另一半，所以我们只需要枚举到sqrt(b)，然后找因子的个数，当枚举到一个因子时，另一个因子就找出来了，如果i * i 恰好为n，则当前只有一个.

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll isPrime(ll n) {
    
    ll cnt = 0;
    for (ll i = 1; i <= sqrt(n); ++i) {
    
        if (n % i == 0) {
    
            if (i * i != n) {
    
                cnt += 2;
            } else {
    
                cnt++;
            }
        }
    }
    return cnt;
}
void solve() {
    
    ll b;
    scanf("%lld", &b);
    printf("%lld\n", isPrime(b));
}
int main() {
    
    solve();
    return 0;
}