约数，外文名：Divisor，别名：因数
简介：
约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。
1.试除法求约数
\(“d\ | \ n”\)代表的含义是 \(d\) 能整除 \(n\) ，（这里的 \(“|”\) 代表整除）
一个合数的约数总是成对出现的，如果 \(d|n\) ，那么 \(\frac{n}{d}|n\)，因此我们求约数的时候，只需要求的那一个数就行了，即只需枚举 \(d<=\frac{n}{d}\)，即 \(d∗d<=n,d<=sqrt(n)\)
vector
{
vector
for(int i = 1; i <= n / i; i ++ ) // n / i意思就是枚举到根号n
{
if(n % i == 0)
{
res.push_back(i);
if(i != n / i) res.push_back(n / i); //有可能出现i * i = n的情况，即两个约数相同，我们只保留一个
}
}
sort(res.begin(), res.end());
return res;
}
2.约数个数
由算术基本定理：任何一个大于1的自然数 ，如果N不为质数，都可以唯一分解成有限个质数的乘积
\(N=P_1^{a1}P_2^{a2}···P_n^{an}\) ，这里 \(P_1 即一个非质数必然可以分解为唯一的一组几个质数的积。 证明： 即\(n\)的正整数约数个数为： \(\prod_{i=1}^n(a_i+1)=(a_1+1)(a_2+1) \ldots (a_n+1)\) #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 ++ ) //把x分解，从2开始枚举，枚举到根号x（x/i这里就相当于根号x） { while(x % i == 0) { x /= i; primes[i] ++; //i的质因数的指数加一 } } if(x > 1) primes[x] ++; //如果x>1，说明x是一个比较大的质因数，然后把剩下的这个数加上就可以了 /*回顾之前讲过的性质：一个合数n中最多只包含一个大于根号n的质因子，所以这里只需要特判一下加上最后那个质因子即可*/ } //上面这步做完后，哈希表primes里就存了所有质因数的指数 LL res = 1; //枚举所有质因数 for(auto c : primes) res = res * (c.second + 1) % mod; //把a1~an的质因子的次数累加起来就可以了 cout << res << endl; return 0; } 3.约数之和 约数和公式： 上式中每个括号里是每个质数的任意次幂之和。 #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] ++; } } if(x > 1) primes[x] ++; } LL res = 1; for(auto prime : primes) { int p = prime.first, a = prime.second; //p为底数，a为指数 LL t = 1; while(a --) //套公式，从0加到a { t = (t * p + 1) % mod; } res = res * t % mod; } cout << res << endl; return 0; } 4.最大公约数 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } 参考： https://zhuanlan.zhihu.com/p/353613695 https://www.cnblogs.com/BaseAI/p/12056017.html