算术基本定理解析及其应用

博客园首页 William 123浏览 0评论

摘要

  本文主要讲述了算术基本定理的内容,具体的应用形式,重点结合例题展示如何使用算术基本定理求解问题。


 

算术基本定理

  算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3……Pnan,这里P1<P2<P3……<Pn均为质数,其中指数ai是正整数。这样的分解称为 N 的标准分解式。

  算术基本定理是初等数论中一条非常基本和重要的定理,它把对自然数的研究转化为对其最基本的元素——素数的研究。唯一因子分解的思想从本质上讲是指以下两种性质: “存在性和唯一性”。所谓“存在性”就是指一个元素可以分解为有限多个不可约因子的乘积;“唯一性”是指这种分解表示在某种意义上来说是唯一的。

定理应用

算法实现

 1 typedef long long ll;
 2 const int maxn  = 1e6 + 7;
 3 ll a[maxn], b[maxn];//a[i]表示第i个质因子,b[i]表示第i个质因子的指数
 4 void fac(ll n, int& tot) {//待分解的整数和不同质因数的个数(按引用传递)
 5     ll tmp = (ll)(sqrt(n) + 0.5);
 6     tot = 0;
 7     ll now = n;
 8     for(int i = 2; i <= tmp; i++) {
 9         if(now % i == 0) {
10             a[++tot] = i;
11             b[tot] = 0;
12             while(now % i == 0) {
13                 ++b[tot];
14                 now /= i;
15             }
16         }
17     }
18     if(now != 1) {//如果剩下的不是1,那就是最大的质因数
19         a[++tot] = now;
20         b[tot] = 1;
21     }
22 }

可以用如下代码直接输出2 到100的质因数分解结果

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int maxn  = 1e6 + 7;
 8 ll a[maxn], b[maxn];//a[i]表示第i个质因子,b[i]表示第i个质因子的指数
 9 void fac(ll n, int& tot) {//待分解的整数和不同质因数的个数(按引用传递)
10     ll tmp = (ll)(sqrt(n) + 0.5);
11     tot = 0;
12     ll now = n;
13     for(int i = 2; i <= tmp; i++) {
14         if(now % i == 0) {
15             a[++tot] = i;
16             b[tot] = 0;
17             while(now % i == 0) {
18                 ++b[tot];
19                 now /= i;
20             }
21         }
22     }
23     if(now != 1) {//如果剩下的不是1,那就是最大的质因数
24         a[++tot] = now;
25         b[tot] = 1;
26     }
27 }
28 
29 int main()
30 {
31     for(ll i = 2; i <=100; i++) {
32         printf("%lld = ", i);
33         int tot = 0;
34         fac(i, tot);
35         for(int i = 1; i <= tot; i++) {
36             printf("%lld^%lld %c ", a[i], b[i], i == tot ? '\n' : '+');
37         }
38     }
39     return 0;
40 }

View Code

例题解析

lightOJ 1341 Aladdin and the Flying Carpet

题意

  给出一个长方形的面积a(不是正方形),给出该长方形最小的边b,问组成该面积的长方形有多少种组合方案。比如12 2,有{2,6}、{3,4}两种组合方案。

解题思路

  问有多少种组合方案,其实就是面积a有多少对因子的乘积等于a,然后去掉最小边不满足条件的对儿数。普通暴力寻找因子对儿数的方法,肯定是要超时的。这里使用唯一分解定理的第一个应用,计算出总的因子数,然后除以2,再减去不符合条件的因子对数即可。需要注意的是每次不必全部试除一遍,不然会超时,这就是这种方法的时间优化之处。

代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 typedef long long ll;
 5 const ll maxn = 1e6 +7;
 6 bool isp[maxn];
 7 int pis[maxn], tot;
 8 
 9 void getp(ll n) {//得到n以内的素数及个数
10     memset(isp, true, sizeof(isp));
11     for(ll i = 2; i <= n; i++) {
12         if(isp[i]) {
13             tot++;
14             pis[tot] = i;
15         }
16         for(int j = 1; (j <= tot) && (i * pis[j] <= n); j++) {
17             isp[i * pis[j]] = false;
18             if(i % pis[j] == 0) break;
19         }
20     }
21 }
22 ll fac(ll n) {//计算n的正因子个数之和
23     ll now = n;
24     ll ans = 1;
25     for(ll i = 1; i <= tot; i++) {
26         if(pis[i] > now)//重要剪枝,每次不必全部试除一遍才结束
27             break;
28         if(now % pis[i] == 0) {
29             int cnt = 0;
30             while(now % pis[i] == 0) {
31                 cnt++;
32                 now /= pis[i];
33             }
34             ans *= (cnt + 1);
35         }
36     }
37     if(now != 1)
38         ans *= 1 + 1;
39     return ans;
40 }
41 ll solve(ll S, ll b) {
42     if(b * b >= S)
43         return 0;
44 
45     ll ans = fac(S);//得到S的正因子个数之和
46     ans /= 2;
47     for(ll i = 1; i < b; i++) {
48         if(S % i == 0)
49             ans--;
50     }
51     return ans;
52 }
53 int main()
54 {
55     ll tot = 0;
56     getp(maxn - 7);//得到maxn - 7以内的素数及个数
57     int T, k = 1;
58     scanf("%d", &T);
59     while(T--) {
60         ll a, b;
61         scanf("%lld%lld", &a, &b);
62         printf("Case %d: %lld\n", k++, solve(a, b));
63     }
64     return 0;
65 }

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;
代码如下
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 typedef long long ll;
 5 const ll maxn = 1e7 +7;
 6 bool isp[maxn];
 7 int pis[maxn/10], tot;
 8 
 9 void getp(ll n) {//得到n以内的素数及个数
10     memset(isp, true, sizeof(isp));
11     for(ll i = 2; i <= n; i++) {
12         if(isp[i]) {
13             tot++;
14             pis[tot] = i;
15         }
16         for(int j = 1; (j <= tot) && (i * pis[j] <= n); j++) {
17             isp[i * pis[j]] = false;
18             if(i % pis[j] == 0) break;
19         }
20     }
21 }
22 ll fac(ll n) {//计算n的正因子个数之和
23     ll now = n;
24     ll ans = 1;
25     for(ll i = 1; i <= tot; i++) {
26         if(pis[i] > now)//重要剪枝,每次不必全部试除一遍才结束
27             break;
28         if(now % pis[i] == 0) {
29             int cnt = 0;
30             while(now % pis[i] == 0) {
31                 cnt++;
32                 now /= pis[i];
33             }
34             ans *= ( 2 * cnt + 1);
35         }
36     }
37     if(now != 1)
38         ans *= 2 * 1 + 1;
39 
40     return ans;
41 }
42 ll solve(ll n) {
43     ll ans = fac(n);//得到n的正因子个数之和
44     return ans / 2 + 1;
45 }
46 int main()
47 {
48     ll tot = 0;
49     getp(maxn - 7);//得到maxn - 7以内的素数及个数
50     int T, k = 1;
51     scanf("%d", &T);
52     while(T--) {
53         ll n;
54         scanf("%lld", &n);
55         printf("Case %d: %lld\n", k++, solve(n));
56     }
57     return 0;
58 }

lightOJ Harmonic Number

题意

给出n(1 ≤ n ≤ 108)计算出调和级数的结果

解题思路

虽然没有直接的公式,但是欧拉曾给出过一个近似公式计算调和级数的和,但是由于前几项误差较大,所以我们先计算前10000的结果,之后的使用公式计算。

代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 
 5 const int maxn = 100010;
 6 using namespace std;
 7 const double C = 0.57721566490153286060651209;
 8 double a[maxn];
 9 
10 int main()
11 {
12     a[0] = 0;
13     for(int i = 1; i <= maxn; i++) {
14         a[i] = a[i - 1] + 1.0/i;
15     }
16     int T;
17     int n;
18     scanf("%d", &T);
19     for(int t = 1; t <= T; t++) {
20         scanf("%d", &n);
21         printf("Case %d: ", t);
22         if(n <= maxn) {
23             printf("%.10lf\n", a[n]);
24         }
25         else {
26             printf("%.10lf\n", log(n) + C + 1.0/(2 * n));
27         }
28     }
29     return 0;
30 }

  最后总结一下使用算术基本定理的心得,使用的时候注意分解,如何使用求得的正因子个数之和,以及所有正因子数之和,来计数。关键还是将问题转换为数学模型。

 


注:www2014.aspxhtml.com转载自cnblogs,若看不到图片,请移步来源网址查看。
via:https://www.cnblogs.com/wenzhixin/p/9885120.html

转载请注明:AspxHtml学习分享网 » 算术基本定理解析及其应用

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址