摘要
本文主要讲述了算术基本定理的内容, 具体的应用形式, 重点结合例题展示如何使用算术基本定理求解问题.
算术基本定理
算术基本定理可表述为: 任何一个大于 1 的自然数 N, 如果 N 不为质数, 那么 N 可以唯一分解成有限个质数的乘积 N=P1a1P2a2P3a3......Pnan, 这里 P1<P2<P3......<Pn 均为质数, 其中指数 ai 是正整数. 这样的分解称为 N 的标准分解式.
算术基本定理是初等数论中一条非常基本和重要的定理, 它把对自然数的研究转化为对其最基本的元素 -- 素数的研究. 唯一因子分解的思想从本质上讲是指以下两种性质: "存在性和唯一性". 所谓 "存在性" 就是指一个元素可以分解为有限多个不可约因子的乘积;"唯一性" 是指这种分解表示在某种意义上来说是唯一的.
定理应用
算法实现
- typedef long long ll;
- const int maxn = 1e6 + 7;
- ll a[maxn], b[maxn];//a[i]表示第 i 个质因子, b[i]表示第 i 个质因子的指数
- void fac(ll n, int& tot) {// 待分解的整数和不同质因数的个数(按引用传递)
- ll tmp = (ll)(sqrt(n) + 0.5);
- tot = 0;
- ll now = n;
- for(int i = 2; i <= tmp; i++) {
- if(now % i == 0) {
- a[++tot] = i;
- b[tot] = 0;
- while(now % i == 0) {
- ++b[tot];
- now /= i;
- }
- }
- }
- if(now != 1) {// 如果剩下的不是 1, 那就是最大的质因数
- a[++tot] = now;
- b[tot] = 1;
- }
- }
可以用如下代码直接输出 2 到 100 的质因数分解结果
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- typedef long long ll;
- const int maxn = 1e6 + 7;
- ll a[maxn], b[maxn];//a[i]表示第 i 个质因子, b[i]表示第 i 个质因子的指数
- void fac(ll n, int& tot) {// 待分解的整数和不同质因数的个数(按引用传递)
- ll tmp = (ll)(sqrt(n) + 0.5);
- tot = 0;
- ll now = n;
- for(int i = 2; i <= tmp; i++) {
- if(now % i == 0) {
- a[++tot] = i;
- b[tot] = 0;
- while(now % i == 0) {
- ++b[tot];
- now /= i;
- }
- }
- }
- if(now != 1) {// 如果剩下的不是 1, 那就是最大的质因数
- a[++tot] = now;
- b[tot] = 1;
- }
- }
- int main()
- {
- for(ll i = 2; i <=100; i++) {
- printf("%lld =", i);
- int tot = 0;
- fac(i, tot);
- for(int i = 1; i <= tot; i++) {
- printf("%lld^%lld %c", a[i], b[i], i == tot ? '\n' : '+');
- }
- }
- return 0;
- }
- View Code
例题解析
lightOJ 1341 Aladdin and the Flying Carpet
题意
给出一个长方形的面积 a(不是正方形), 给出该长方形最小的边 b, 问组成该面积的长方形有多少种组合方案. 比如 12 2, 有 {2,6},{3,4} 两种组合方案.
解题思路
问有多少种组合方案, 其实就是面积 a 有多少对因子的乘积等于 a, 然后去掉最小边不满足条件的对儿数. 普通暴力寻找因子对儿数的方法, 肯定是要超时的. 这里使用唯一分解定理的第一个应用, 计算出总的因子数, 然后除以 2, 再减去不符合条件的因子对数即可. 需要注意的是每次不必全部试除一遍, 不然会超时, 这就是这种方法的时间优化之处.
代码
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- typedef long long ll;
- const ll maxn = 1e6 +7;
- bool isp[maxn];
- int pis[maxn], tot;
- void getp(ll n) {// 得到 n 以内的素数及个数
- memset(isp, true, sizeof(isp));
- for(ll i = 2; i <= n; i++) {
- if(isp[i]) {
- tot++;
- pis[tot] = i;
- }
- for(int j = 1; (j <= tot) && (i * pis[j] <= n); j++) {
- isp[i * pis[j]] = false;
- if(i % pis[j] == 0) break;
- }
- }
- }
- ll fac(ll n) {// 计算 n 的正因子个数之和
- ll now = n;
- ll ans = 1;
- for(ll i = 1; i <= tot; i++) {
- if(pis[i]> now)// 重要剪枝, 每次不必全部试除一遍才结束
- break;
- if(now % pis[i] == 0) {
- int cnt = 0;
- while(now % pis[i] == 0) {
- cnt++;
- now /= pis[i];
- }
- ans *= (cnt + 1);
- }
- }
- if(now != 1)
- ans *= 1 + 1;
- return ans;
- }
- ll solve(ll S, ll b) {
- if(b * b>= S)
- return 0;
- ll ans = fac(S);// 得到 S 的正因子个数之和
- ans /= 2;
- for(ll i = 1; i <b; i++) {
- if(S % i == 0)
- ans--;
- }
- return ans;
- }
- int main()
- {
- ll tot = 0;
- getp(maxn - 7);// 得到 maxn - 7 以内的素数及个数
- int T, k = 1;
- scanf("%d", &T);
- while(T--) {
- ll a, b;
- scanf("%lld%lld", &a, &b);
- printf("Case %d: %lld\n", k++, solve(a, b));
- }
- return 0;
- }
- lightOJ 1236 Pairs Forming LCM
题意
给一个 n(1 ≤ n ≤ 1014), 问满足 lcm(i, j) = n (1 =< i, j <= n 且 i <= j)的 (i, j) 有多少对
解题思路
一看 n 的大小就知道暴力肯定是不行了, 我们试着用算术基本定理求解一下, 将 n = p1^x1 * p2^x2 * p3^x3...ps^xs(其中 s 是唯一分解式中所有质因子的个数)
先假设 n = p1^x1;
要使 lcm(i, j) = n, 只有两种方法:
(1)i = p1^x1, 则 j = p1^m(m 属于 [0, x1]), 这样(i, j) 共有 (x1 + 1)种
(2)j = p1^x1, 则 i = p1^n(n 属于 [0, x1]), 这样(i, j) 共有 (x1 + 1)种
那么当 n = p1^x1 时答案就是 2 * (x1 + 1)对(i, j), 但是当 m == n 时这一对是计算重复的, 所以需要 -1, 则最终答案是 2 * (x1 + 1) - 1 = 2 * x1 + 1;
推广至 n = p1^x1 * p2^x2 * p3^x3...ps^xs(其中 s 是唯一分解式中所有质因子的个数)可得总的方案数等于 ans = (2 * x1 + 1) * (2 * x2 + 1) * (2 * x3 + 1) ...(2 * xs + 1);
题目中要求的是 i <= j, 所以需要将总的数目除以 2, 又由于当 i ,j 都等于 n 时只计算了一次, 所以除以二之后需要再加上. 故最终答案是 ans = ans/2 + 1;
代码如下
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- typedef long long ll;
- const ll maxn = 1e7 +7;
- bool isp[maxn];
- int pis[maxn/10], tot;
- void getp(ll n) {// 得到 n 以内的素数及个数
- memset(isp, true, sizeof(isp));
- for(ll i = 2; i <= n; i++) {
- if(isp[i]) {
- tot++;
- pis[tot] = i;
- }
- for(int j = 1; (j <= tot) && (i * pis[j] <= n); j++) {
- isp[i * pis[j]] = false;
- if(i % pis[j] == 0) break;
- }
- }
- }
- ll fac(ll n) {// 计算 n 的正因子个数之和
- ll now = n;
- ll ans = 1;
- for(ll i = 1; i <= tot; i++) {
- if(pis[i]> now)// 重要剪枝, 每次不必全部试除一遍才结束
- break;
- if(now % pis[i] == 0) {
- int cnt = 0;
- while(now % pis[i] == 0) {
- cnt++;
- now /= pis[i];
- }
- ans *= ( 2 * cnt + 1);
- }
- }
- if(now != 1)
- ans *= 2 * 1 + 1;
- return ans;
- }
- ll solve(ll n) {
- ll ans = fac(n);// 得到 n 的正因子个数之和
- return ans / 2 + 1;
- }
- int main()
- {
- ll tot = 0;
- getp(maxn - 7);// 得到 maxn - 7 以内的素数及个数
- int T, k = 1;
- scanf("%d", &T);
- while(T--) {
- ll n;
- scanf("%lld", &n);
- printf("Case %d: %lld\n", k++, solve(n));
- }
- return 0;
- }
- lightOJ Harmonic Number
题意
给出 n(1 ≤ n ≤ 108)计算出调和级数的结果
解题思路
虽然没有直接的公式, 但是欧拉曾给出过一个近似公式计算调和级数的和, 但是由于前几项误差较大, 所以我们先计算前 10000 的结果, 之后的使用公式计算.
代码
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- const int maxn = 100010;
- using namespace std;
- const double C = 0.57721566490153286060651209;
- double a[maxn];
- int main()
- {
- a[0] = 0;
- for(int i = 1; i <= maxn; i++) {
- a[i] = a[i - 1] + 1.0/i;
- }
- int T;
- int n;
- scanf("%d", &T);
- for(int t = 1; t <= T; t++) {
- scanf("%d", &n);
- printf("Case %d:", t);
- if(n <= maxn) {
- printf("%.10lf\n", a[n]);
- }
- else {
- printf("%.10lf\n", log(n) + C + 1.0/(2 * n));
- }
- }
- return 0;
- }
最后总结一下使用算术基本定理的心得, 使用的时候注意分解, 如何使用求得的正因子个数之和, 以及所有正因子数之和, 来计数. 关键还是将问题转换为数学模型.
来源: https://www.cnblogs.com/wenzhixin/p/9885120.html