试除法求约数
方法1-试除所有数
算法原理
假设p是x的一个约数,那么x/p一定也是它的约数,所以只需枚举2 到 $\sqrt[2]{n}$的约数,并且可以直接通过运算获得 $\sqrt[2]{n}$ 之后对应的那个约数 时间复杂度$O(\sqrt{n})$
代码实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; ++ i)
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int x;
cin >> x;
auto res = get_divisors(x);
for (int t : res) cout << t << ' ';
cout << endl;
}
return 0;
}
方法2:质因数分解 + dfs
算法原理 此做法的原理和计算所有约数的和有些类似,属于排列组合问题。 对于每个质数,我们选择其一种指数情况,所有质数相乘在一些就属于一个约数,暴搜所有情况即可(暴搜具有可行性的原因是int范围内具有约数最多的数具有1600个约数,情况很少,暴搜是可以实现的)
算法流程
- 首先使用线性筛获取所需范围的质数
- 对数据进行质因数分解
- dfs获取所有约数
代码实现
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 50010;
int primes[N], cnt;
bool st[N];
PII primes_factor[N];
int divisors[N];
int cntf, cntd;
void init(int n)
{
for (int i = 2; i <= n; ++ i)
{
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] * i <= n; ++ j)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void dfs(int u, int p)
{
if (u == cntf)
{
divisors[cntd ++] = p;
return ;
}
for (int i = 0; i <= primes_factor[u].second; ++ i)
{
dfs(u + 1, p);
p *= primes_factor[u].first;
}
}
void get_divisors(int n)
{
cntf = 0;
for (int i = 0; i < cnt; ++ i)
{
int p = primes[i];
if (n % p == 0)
{
int s = 0;
while (n % p == 0)
{
++ s;
n /= p;
}
primes_factor[cntf ++] = {p, s};
}
}
if (n > 1) primes_factor[cntf ++] = {n, 1};
cntd = 0;
dfs(0, 1);
}
int main()
{
init(50000);
int n;
cin >> n;
while (n --)
{
int x;
cin >> x;
get_divisors(x);
sort(divisors, divisors + cntd);
for (int i = 0; i < cntd; ++ i) cout << divisors[i] << ' ';
cout << endl;
}
return 0;
}
计算约数个数
int范围内具有最多约数的数拥有$1600$个约数
算法原理
根据唯一分解定理,任意数n可表示为 $ n = p_1^{\alpha_1} * p_2^{\alpha_2} * ... * p_n^{\alpha_n} $, 选择一定量的 $ P_1 , P_2, ... ,P_n $ 相乘获得n的约数,总的选择方案为$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$,其中加1表示指数可以为0
代码实现
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
inline void get_divisors(int x)
{
for (int i = 2; i <= x / i; ++ i)
while (x % i == 0)
{
x /= i;
++ primes[i];
}
if (x > 1) ++ primes[x];
}
int main()
{
int x;
cin >> x;
get_divisors(x);
long long res = 1;
for (auto prime : primes) res = res * (prime.second + 1) % MOD;
cout << res << endl;
return 0;
}
计算所有约数的和
算法思想
$(p_1^{\alpha_1} + p_1^{\alpha_2} + ... + p_2^{\alpha_n}) * (p_2^{\alpha_1} + p_2^{\alpha_2} + ... + p_2^{\alpha_n}) * ... * (p_n^{\alpha_1} + p_n^{\alpha_2} + ... + p_n^{\alpha_n})$,展开之后一共是$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$项,每一项的形式均为$ p_1^{k_1} * p_2^{k_2} * ... * p_n^{k_n} $,即每一项都是一个约数,所有约数加在一起即为答案
代码实现
代码中计算 $ p_1^{0} + p_1^{1} + ... + p_2^{\alpha_1}$ 时候采用了非常巧妙的做法。可以概括为当我们计算 $\sum_{i = 0}^{\alpha}p^i$ 这种求和时,可以采用下面的代码
int t = 1; // 最终结果
while(a --) // a表示p的最大指数
t = t * p + 1;
#include <iostream>
#include <unordered_map>
using namespace std;
int n;
const int MOD = 1e9 + 7;
unordered_map<int, int> primes;
void get_divisors(int x)
{
for (int i = 2; i <= x / i; ++ i)
while (x % i == 0)
{
x /= i;
++ primes[i];
}
if (x > 1) ++ primes[x];
}
int main()
{
int x;
cin >> x;
get_divisors(x);
long long res = 1;
for (auto prime : primes)
{
int p = prime.first, a = prime.second;
long long t = 1;
while (a --) t = (t * p + 1) % MOD;
res = res * t % MOD;
}
cout << res << endl;
return 0;
}
计算倍数个数
1到n中p的倍数(或者说能被p整除)的数有 $\lfloor \frac{n}{p} \rfloor$ 个
原理很简单,1到n中p的倍数为 $1p, 2p, 3p, ... kp$,当$kp$恰好等于n时,总个数为 $\frac {n}{p}$;当$kp<n$ 且 $(k+1)*p>n$ 时,总个数为 $\lfloor \frac{n}{p} \rfloor$。将两种情况结合在一起就是$\lfloor \frac{n}{p} \rfloor$
1到n中既是$p_1$的倍数,又是$p_2$的倍数有 $\lfloor \frac{n}{p_1 \ * \ p_2} \rfloor$ 个($p_1$ 和 $p_2$保证互质)
首先我们假设$p_1$和$p_2$是两个不相等的质数且m既是$p_1$的倍数(为了后续公式的简便,这里假设就是1倍的关系),又是$p_2$的倍数(同前),根据唯一分解定理,m的质因数分解式中一定是$p_1 \ * \ p_2 \ * \ ...$的形式,所以m一定可以整除 $p_1 \ * \ p_2$,所以也就是求1到n中$p_1 \ * \ p_2$倍数的个数。 上述公式中,对于$p_1$ 和 $p_2$的要求是保证互质即可,并没有限制必须均为质数,原因在于即使两个数中存在合数,比如4和7,但是由于两个数是互质的,所以两者质因数分解的结果中一定不包含相同的质因子,所以和上面两个数均是质数的情况一样,如果某数m是4和7的倍数,那么它一定是4*7的倍数。 综上所述,上述公式是正确的。
标签:约数,总结,...,int,alpha,include,divisors From: https://blog.51cto.com/u_14882565/7128294