AcWing 871. 约数之和
本题链接：AcWing 871. 约数之和
本博客提供本题截图：
本题解析
计算约数之和的公式：首先把这个数写成质因数的乘积的形式：
这个数的约数之和就是：
如何凑出：
利用：
AC代码
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; typedef long long LL; const int N = 110, mod = 1e9 + 7; int main() { int n; cin >> n; unordered_map<int, int> primes; while (n -- ) { int x; cin >> x; for (int i = 2; i <= x / i; i ++ ) while (x % i == 0) { x /= i; primes[i] ++ ; } if (x > 1) primes[x] ++ ; } LL res = 1; for (auto p : primes) { LL a = p.first, b = p.second; LL t = 1; while (b -- ) t = (t * a + 1) % mod; res = res * t % mod; } cout << res << endl; return 0; }
AcWing 872. 最大公约数
本题链接：AcWing 872. 最大公约数
本博客提供本题截图：
本题解析
求最大公约数模板：（需要背过）
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
AC代码
#include <iostream> #include <algorithm> using namespace std; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n; cin >> n; while (n -- ) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", gcd(a, b)); } return 0; }
三、时间复杂度
关于约数各步操作的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
