43 lines
1.3 KiB
C++
43 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
//约数个数定理
|
||
//约数个数定理可以计算出一个数约数的个数，在小学奥数与中学竞赛中大有用处。
|
||
//https://baike.baidu.com/item/%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0%E5%AE%9A%E7%90%86/4926961
|
||
//根据乘法原理：n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。
|
||
//例题：正整数378000共有多少个正约数？
|
||
//解：将378000分解质因数378000=24×33×53×71
|
||
//由约数个数定理可知378000共有正约数(4+1)×(3+1)×(3+1)×(1+1)=160个。
|
||
|
||
/**
|
||
* C++版本的约数个数定理
|
||
* https://blog.csdn.net/qq_40924940/article/details/86525912
|
||
* @param n
|
||
* @return
|
||
*/
|
||
LL getNum(LL n) {
|
||
LL res = 1;
|
||
if (n == 1) return 1;
|
||
for (LL i = 2; i * i <= n; i++) {
|
||
LL k = 0;
|
||
while (n % i == 0) {
|
||
n = n / i;
|
||
k++;
|
||
}
|
||
if (k) res *= (k + 1);
|
||
}
|
||
if (n != 1) res = res * 2;
|
||
if (res == 1) return 2;
|
||
return res;
|
||
}
|
||
|
||
int main() {
|
||
long long b = pow(2, 7) * pow(3, 8) * pow(5, 9);
|
||
cout << b << endl;
|
||
//约数个数 (7+1)*(8+1)*(9+1)=720个
|
||
|
||
//按数学推导的约数个数定理输出约数个数
|
||
cout << getNum(b) << endl;
|
||
return 0;
|
||
} |