时间复杂度 \(O(n\sqrt a)\)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> res;
int n, a;
int main()
{
cin >> n;
while (n--) {
res.clear();
cin >> a;
for (int i = 1; i <= a / i; ++i) {
if (a % i == 0) {
if (a / i == i) res.push_back(i);
else res.push_back(i), res.push_back(a / i);
}
}
sort(res.begin(), res.end());
for (int it : res)
cout << it << " ";
cout << endl;
}
return 0;
}
\(N=\prod\limits_{i=1}^{k}p_i^{d_i}\)
公式 \(\prod\limits_{i=1}^k(d_i+1)\)
怎么理解公式呢？可以分两种情况。
我们先设 \(b=\prod\limits_{j=1}^{i-1}(d_j+1)\)
情况一 \(i > 1\)
用乘法分配律得 \(b \cdot d_i + b\)
其中 \(b \cdot d_i\) 是用乘法原理新组成的约数，\(b\) 是旧的约数。
情况二 \(i=1\)
约数个数就是 \(d^i+1\)
\(d_i\) 新的，而 \(1\) 是每个因数必有的 \(1\)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
int n, a;
unordered_map<int, int> d;
int main()
{
cin >> n;
while (n--) {
cin >> a;
for (int i = 2; i <= a / i; ++i) {
while (a % i == 0) {
++d[i];
a /= i;
}
}
if (a > 1) ++d[a];
}
long long ans = 1;
for (auto it : d) {
ans = ans * (it.second + 1) % MOD;
}
printf("%lld\n", ans);
return 0;
}
\(N=\prod\limits_{i=1}^{k}p_i^{d_i}\)
公式 \(\prod\limits_{i=1}^k\sum\limits_{j=0}^{d_i}p_{i}^{j}\)
证明很简单用乘法分配律展开就是了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
int n, a;
unordered_map<int, int> d;
int main() {
cin >> n;
while (n--) {
cin >> a;
for (int i = 2; i <= a / i; ++i) {
while (a % i == 0) {
++d[i];
a /= i;
}
}
if (a > 1) ++d[a];
}
long long ans = 1;
for (auto it : d) {
long long t = 0, tt = 1;
for (int i = 0; i <= it.second; ++i)
t = (t + tt) % MOD, tt = it.first * tt % MOD;
ans = ans * t % MOD;
}
printf("%d\n", ans);
return 0;
}
热知识：一般 \(\gcd(a,b)\) 都写成 \((a,b)\)
公式 \((a,b)=(b,a \mod b)\)
证明：
\(\begin{aligned}a \mod b&=a-\lfloor{\frac{a}{b}}\rfloor\cdot b\\&=a-x\cdot b \end{aligned}\)
我们设 \(d=(a,b)\)
那么 \(d \mid a,d\mid b,d\mid a+b, d\mid ax+by\)
所以 \((a,b)=(b,a-\lfloor{\frac{a}{b}}\rfloor\cdot b)=(b,a\mod b)\)
证毕
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, a, b;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
cin >> n;
while (n--) {
cin >> a >> b;
cout << gcd(a, b) << endl;
}
return 0;
}