86 lines
2.0 KiB
C++
86 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
//约数和定理
|
||
//https://baike.baidu.com/item/%E7%BA%A6%E6%95%B0%E5%92%8C%E5%AE%9A%E7%90%86/3808428
|
||
/**
|
||
例题：正整数360的所有正约数的和是多少？
|
||
解：将360分解质因数可得
|
||
360=2^3*3^2*5^1
|
||
|
||
由约数和定理可知，360所有正约数的和为
|
||
(2^0+2^1+2^2+2^3)×(3^0+3^1+3^2)×(5^0+5^1)=(1+2+4+8)(1+3+9)(1+5)=15×13×6=1170
|
||
|
||
可知360的约数有1、2、3、4、5、6、8、9、10、12、15、18、20、24、30、36、40、45、60、72、90、120、180、360；
|
||
则它们的和为1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360=1170
|
||
*/
|
||
|
||
const int N = 1010;
|
||
int a[N];
|
||
int cnt;
|
||
|
||
//下面是求所有约数的方法
|
||
void ben(int n) {
|
||
for (int i = 1; i <= sqrt(n); i++) {
|
||
if (n % i == 0) {
|
||
a[++cnt] = i;
|
||
if (n != i * i)
|
||
a[++cnt] = n / i;
|
||
}
|
||
}
|
||
}
|
||
|
||
/**
|
||
* 功能：快速幂
|
||
* @param m
|
||
* @param k
|
||
* @return
|
||
*/
|
||
int qmi(int m, int k) {
|
||
int res = 1, t = m;
|
||
while (k) {
|
||
if (k & 1) res = res * t;
|
||
t = t * t;
|
||
k >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
/**
|
||
* C++版本的约数和定理
|
||
* https://blog.csdn.net/qq_40924940/article/details/86525912
|
||
* @param n
|
||
* @return
|
||
*/
|
||
LL getSum(LL n) {
|
||
LL res = 1;
|
||
for (LL i = 2; i * i <= n; i++) {
|
||
LL k = 0;
|
||
while (n % i == 0) {
|
||
n = n / i;
|
||
k++;
|
||
}
|
||
res = res * ((1 - qmi(i, k + 1)) / (1 - i));
|
||
}
|
||
if (n != 1) res *= (1 + n);
|
||
return res;
|
||
}
|
||
|
||
int main() {
|
||
//1、算出所有约数再求和
|
||
ben(360);
|
||
//排序一下，否则顺序有点看不懂
|
||
sort(a + 1, a + 1 + cnt);
|
||
for (int i = 1; i <= cnt; i++)cout << a[i] << " ";
|
||
cout << endl;
|
||
|
||
//计算一下总和
|
||
long long sum = 0;
|
||
for (int i = 1; i <= cnt; i++)sum += a[i];
|
||
cout << sum << endl;
|
||
|
||
//2、根据公式算一下约数和
|
||
cout << getSum(360) << endl;
|
||
return 0;
|
||
} |