求一个数的约数(试除法求约数)
跟判断一个数是否是质数一样，同样采用试除法来判断
练习链接: 869. 试除法求约数
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
auto f(int n)
{
vector<int> v;
for(int i = 1; i <= n / i; ++i) // 同样因数的话只用判断一半, 因为判断出一个因数时，也同时得到了另外一个因数
{
if(n % i == 0)
{
v.push_back(i);
if(i != n / i) v.push_back(n / i); // 特判开根号的情况
}
}
sort(v.begin(), v.end()); // 题目要求从小到大输出
for(auto a: v) cout << a << " ";
cout << endl;
}
auto main() -> int
{
int n; cin >> n;
while(n--)
{
int a; cin >> a;
f(a);
}
}
约数的个数
其实这就是一个公式 ： 约数个数定理
首先根据定义，n可以分解质因数：n=p1^a1×p2^a2×p3^a3…pk^ak,
其中一个因数为 n=p1^b1×p2^b2×p3^b3…pk^bk 故此时对于b1可以在 (0 ~ a1)间取值，共a1 + 1 种, 同理b2 也有 a2 + 1 种取值. 故根据乘法原理：n的约数的个数就是(a1+1)(a2+1)(a3+1)…(ak+1)。
练习链接 : 870. 约数个数
#include<iostream>
#include<unordered_map>
using namespace std;
constexpr int mod = 1e+9 + 7;
// 故根据上面的公式我们只要把要求的数分解成底数和其对应的指数即可
auto main() -> int
{
unordered_map<int, int> m;
int n; cin >> n;
while(n--)
{
int a; cin >> a;
for(int i = 2; i <= a / i; ++i)
while(a % i == 0) m[i]++, a /= i; // map数组first记录底数, second 记录指数
if(a > 1) m[a]++;
}
long long res = 1;
for(auto item : m) res = res * (item.second + 1) % mod; // 根据公式进行计算
cout << res << endl;
return 0;
}
约数之和 –> 约数和定理
约数和定理: 对于一个大于1正整数n可以分解质因数：n=p1^a1p2^a2p3^a3…pk^ak,那么其正约数和为
f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）
练习链接: 871. 约数之和
#include<iostream>
#include<unordered_map>
using namespace std;
constexpr int mod = 1e+9 + 7;
auto main() -> int
{
unordered_map<int, int> m;
int n; cin >> n;
while(n--)
{
int a; cin >> a;
for(int i = 2; i <= a / i; ++i)
while(a % i == 0) m[i]++, a /= i; // 跟之前求约数个数一样，先对这个数进行分解,分解成底数和指数的格式
if(a > 1) m[a]++;
}
long long res = 1;
for(auto item : m)
{
long long t = 1;
for(int i = 1; i <= item.second; ++i)
t = (t * item.first + 1) % mod; // 相当于算出(pk0 + pk1 + pk2 + ... + pkx);
res = res * t % mod; // 根据约数和公式将这些项相乘
}
cout << res << endl;
}
求最大公约数 (辗转相除法 / 欧几里得算法)
首先来看这样一个例子, d能整除a, 记做 d | a, 同样d能整除b, 记 d | b, 故同样得到的一个结论就是 d | xa + yb， 这是一个基本的性质了。 故现在要推导的一个定理为（a, b） 的最大公约数等于 (a. a mod b) 的最大公约数, 首先我们看 (a, b), 其中一个公约数为d, 故对于左边 d | a, d | b, 对于(a, a mod b），同样是d | a (因为这一项跟左边是一样的一项, 那 d | a mod b 吗? 我们将 a mod b 展开一下 a mod b = a - | a / b | * b （这里| a / b | 表示下取整，直接记为c = | a / b | 故 a mod b = a - c * b; 故d一定可以整除 , d | a - c * b; 这说明左边的公约数一定是右边的公约数, 那么右边的公约数是左边的公约数吗, 从右边看，(b, a mod b)， 即(b, a - c * b)的公约数为d， 则存在 d | b , d | a - c * b; 故对于左边d | b 一定成立, 那么再看 d | a - c * b , 由于已经存在了 d | b , 故再加上c * b , d | a - c * b + c * b 还是成立的，故得到了 d | a, 故这就证明了右边的公约数也是左边的公约数，两边的公约数一样,那么其最大公约数肯定也一样。故这样的话只需一行代码即可求出两个数的最大公约数
练习链接: 872. 最大公约数
#include<iostream>
using namespace std;
auto f(int a, int b) -> int
{
// 判断一下此时第二项是否为0， 若为0，（1）上来就是b = 0直接返回a即可,因为0的因数可以是任何其他数
// (1)若不是继续递归, 根据上面的推导 (a, b) 和 (b, a mod b) 的最大公约数相同
// 直到第二项等于0时， 也就对应第一项是最大的了
return b ? f(b, a % b) : a;
}
auto main() -> int
{
int n; cin >> n;
while(n--)
{
int a, b; cin >> a >> b;
cout << f(a, b) << endl;
}
}
赞