免费建立自己的个人网站,金华职院优质校建设网站,全球搜,导航网站怎么做seo唯一分解定理
唯一分解定理指的是#xff1a;对于任意一个1的正整数#xff0c;都可以以唯一的一种方式分解为若干质因数的乘积。 x p 1 k 1 ⋅ p 2 k 2 ⋅ … ⋅ p m k m x p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_m^{k_m} xp1k1⋅p2k2⋅…⋅pmkm…唯一分解定理
唯一分解定理指的是对于任意一个1的正整数都可以以唯一的一种方式分解为若干质因数的乘积。 x p 1 k 1 ⋅ p 2 k 2 ⋅ … ⋅ p m k m x p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_m^{k_m} xp1k1⋅p2k2⋅…⋅pmkm 这个式子中的p1p2是类似2357这样的质数。 将单个数字进行质因数方法是从小到大枚举x的所有可能的质因子最大枚举到sqrtx每遇到一个可以整除的数字i就不断进行除法直到除尽。最后如果还有x1说明还有一个较大的质因子。
#include bits/stdc.h
using namespace std;const int N 2e5 9;
vectorpairint, int v;int main() {int x;cin x;// Enumerate all possible prime factorsfor (int i 2; i x / i; i) {// If it doesnt divide, skipif (x % i) continue;// If it divides, it must be a prime factor (due to the nature of enumeration from small to large)// Count represents the exponent of the current prime factor (i)int cnt 0;// Keep dividing until it is no longer divisiblewhile (x % i 0) {cnt;x / i;}v.push_back({i, cnt});}// If x is greater than 1, it means x itself is a prime factorif (x 1) {v.push_back({x, 1});}// Print the prime factors and their exponentsfor (const auto i : v) {cout i.first i.second \n;}return 0;
}约数个数定理
通过某个数字的唯一分解 x p 1 k 1 ⋅ p 2 k 2 ⋅ … ⋅ p m k m x p_1^{k_1} \cdot p_2^{k_2} \cdot \ldots \cdot p_m^{k_m} xp1k1⋅p2k2⋅…⋅pmkm 我们可以求出x的约数因数个数如果学过线性代数或者有向量相关的知识的话可以理解为将不同的质因子看作是不同的向量空间或基底不同质因子之间互不干扰。 也就是说p1的指数的取值是0k1共k11个p2p3…亦然所以x的约数的个数就是 k11k21…km1即 d ( x ) ∏ i 1 m ( k i 1 ) d(x) \prod_{i1}^{m}(k_i 1) d(x)i1∏m(ki1)
阶乘约数
思路100阶乘太大不能直接求出再求正约数。可以用唯一分解定理和约数个数定理来求约数个数。
#includeiostream
using namespace std;
const int N 1e2 5;
int a[N];void f(int x){for(int i2;ix/i;i){if(x%i)continue;int cnt 0;while(x%i0){cnt;x/i;}a[i]cnt;}if(x1)a[x];
}int main(){for(int i 1;i100;i)f(i);long long ans 1;for(int i1;i100;i)ans*(a[i]1);coutans\n;return 0;
} 求值 #includeiostream
using namespace std;int check(int x) {int cnt 0;for(int i1;i*ix;i){if(x%i0){if(ix/i)cnt;else cnt2;}}return cnt 100;
}int main() {for(int i1; ;i){if(check(i)){couti\n;break;}}return 0;
}
