目录
试除法求约数求约数个数约数之和欧几里得算法
试除法求约数
试除法求一个数的所有约数，思路与判断质数的思路一样，优化的方法也是一样的，这里就不再赘述，没有看过我之前关于质数的博客可以点这里。 从小到大枚举所有约数，但是我们只需要枚举每一对儿中较小的一个就可以了。 时间复杂度：O(sqrt(n))
vector
{
vector
for(int i = 1; i <= n/i; i ++ )
{
if(n % i == 0)
{
res.push_back(i);
if(n/i != i) res.push_back(n/i);
}
}
sort(res.begin(),res.end()); //排序
return res;
}
求约数个数
基于算数基本定理 约数个数定理 定理证明 也可点击👉：约数个数定理 注：int范围内约数个数最多的一个数，它的约数是1500个左右。
例 给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map
while(n -- )
{
int x;
cin >> x;
for(int i = 2; i <= x/i ; i ++ )
while(x % i == 0)
{
x /= i;
primes[i] ++ ; //i这个质因数的指数＋1
//primes的下标是质数，存的值是这个质数的指数
}
if(x > 1) primes[x] ++; //x是大于的sqrt(x)约数
}
LL res = 1;
for(auto prime : primes)
res = res*(prime.second + 1) % mod;
cout << res;
return 0;
}
约数之和
约数和定理 对于一个大于1正整数n可以分解质因数：n=p1a1×p2a2×p3a3×…×pkak, 则由约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个， 那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为 f(n)=(p10+p11+p12+…p1a1)(p20+p21+p22+…p2a2)…(pk0+pk1+pk2+…pkak）
证明 证明：若n可以分解质因数：n=p1a1×p2a2×p3a3×…×pkak, 可知p1a1的约数有:p10, p11, p12…p1a1 … 同理可知，pkak的约数有:pk^0, pk^1, pk2…pkak^ ； 实际上n的约数是在p1a1、p2a2、…、pkak每一个的约数中分别挑一个相乘得来， 可知共有(a₁+1)(a₂+1)(a₃+1)…(ak+1)种挑法，即约数的个数。 由乘法原理可知它们的和为 f(n)=(p10+p11+p12+…p1a1)(p20+p21+p22+…p2a2)…(pk0+pk1+pk2+…pkak）
也可以点击👉：约数和定理 例 给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 109+7 取模。 思路：同样，先分解质因数，带入上面约数和的公式即可。
#include
#include
#include
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
unordered_map
while(n -- )
{
int x;
cin >> x;
for(int i = 2; i <= x/i ; i ++ )
while(x % i == 0)
{
x /= i;
primes[i] ++ ; //i这个质因数的指数＋1
//primes的下标是质数，存的值是这个质数的指数
}
if(x > 1) primes[x] ++; //x是大于的sqrt(x)约数
}
LL res = 1;
for(auto prime : primes)
{
int p = prime.first; //质数的底数
int a = prime.second; //质数的指数
LL t = 1;
while(a -- ) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout << res << endl;
return 0;
}
注 while(a- -) t=(t*p+1)%mod; 循环第一次：t=p+1 循环第二次：t=p2+p+1 循环第三次：t=p3+p2+p+1 … 循环第a次：t=p0+p1+p2+…pa 当然这只是算出了(p10+p11+p12+…p1a1)，我们还要算p2、p3、…、pk并相乘
欧几里得算法
欧几里得算法，即辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。 核心原理：gcd(a,b) = gcd(b,a mod b) 一个基本的性质：d | a，d | b，d | (a+b)，d | (ax + by) （d能整除a，d能整除b，那么d就能整除a+b，也能整除a的若干倍+b的若干倍）
int gcd(int a,int b)
{
return b ? gcd(b,a % b) : a;
}
b不为0时，最大公约数是gcd(b, a mod b) b为0时，最大公约数就是a（0可以整除任何数）