信息学奥赛中的数学知识——约数

约数个数

任何一个大于1的自然数 N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积： $N=p_1^{a_1}\times p_2^{a_2}\times p_3^{a_3}...p_n^{a_n}$，这里$p_1<p_2<p_3...<p_n$均为质数， 其中指数$a_i$是正整数。这样的分解称为 N 的标准分解式。

N 的约数个数 =$(a_1+1)\times (a_2+1)\times (a_3+1)\times ...\times (a_n+1)$

#include <iostream> #include <map> using namespace std; /* 如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1) */ const int mod = 1e9 + 7; typedef long long LL; int main() { int n; cin >> n; map<int, int> h; while(n --) { int x; cin >> x; for(int i = 2; i <= x / i; i ++) { while(x % i == 0) { h[i] ++; x /= i; } } // 任何一个数字x，最多只包含一个大于sqrt(x)的质因子 if(x > 1) h[x] ++; } int res = 1; for(map<int, int>::iterator it = h.begin(); it != h.end(); it ++) { res = (LL) res * (it -> second + 1) % mod; } cout << res << endl; return 0; }

约数之和

N 的约数之和 =$(p_1^0+p_1^1+p_1^2+...+p_1^{a_1})\times (p_2^0+p_2^1+p_2^2+...+p_2^{a_2})\times ...\times (p_n^0+p_n^1+p_n^2+...+p_n^{a_n})$

#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; //divs[i] = j 表示因子i的个数为j unordered_map<int, int> divs; int main(){ int n; cin>>n; while(n--){ int x; cin>>x; //求x的约数，及其个数 for(int i = 2; i <= x / i; i++){ while(x % i == 0) { divs[i]++; x /= i; } } if(x > 1) divs[x]++; } long long res = 1; for(auto d : divs){ int p = d.first, a = d.second; long long t = 1; // t[1] = 1 + p^1 // t[2] = 1 + (1 + p) * p = 1 + p^1 + p^2 // t[k - 1] = 1 + p^1 + p^2 + ... + p^{k-1} // t[k] = 1 + t[k-1] * p= 1 + ( 1 + p^1 + p^2 + p^{k-1}) * p = 1 + p^1 + p^2 +...+ p^{k-1} + p^k while(a--) t = (1 + t * p) % mod; res = res * t % mod; } cout<<res<<endl; return 0; }