精华内容
下载资源
问答
  • (美国)罗森(Kenneth H.Rosen)《初等数论及其应用(英文版)(第6版)》最新版。
  • 初等数论及其应用(原书第5版)奇数题答案
  • 初等数论及其应用-第五版-华章-Kenneth.H.Rosen
  • 初等数论及其应用(英文版)(第5版)》是数论课程的经典教材,自出版以来,深受读者好评,被美国加州大学伯克利分校、伊利诺伊大学、得克萨斯大学等数百所名校采用。 《初等数论及其应用(英文版)(第5版)》以经典理论...
  • 这个专栏叫做“初等数论及其应用”,没有按照以前的习惯,用哪本教材命名,实际上我原本也是想结合华章译丛的《初等数论及其应用》,但是手头其实很多资料能说到数论(《训练指南》、《具体数学》等等),因此这里...

      写在前面:开这个专栏之前其实是很纠结的,为了博客专栏的分类纠结了一会。这个专栏叫做“初等数论及其应用”,没有按照以前的习惯,用哪本教材命名,实际上我原本也是想结合华章译丛的《初等数论及其应用》,但是手头其实很多资料能说到数论(《训练指南》、《具体数学》等等),因此这里不用哪本书名命名了,而以这个分支的名字命名,专栏下的博客也以数论下的专题或者知识点为标题。这个专栏的作用,主要体现在对数论这个大专题的总结反思与复习,在整理以前略显杂乱的博客以外,顺便做一些提升性的练习(因为笔者发现搞过理论性的东西后,应用的能力真的有待提高……)。因此在博客内容上,然后以应用思维主要侧重点,理论部分主要呈现应用中较为重要的部分。

     

     

       

     

       

     

      唯一分解定理一个最重要的应用,就是在于计算非常大的数据时(例如组合数、大的阶乘数),便可以将运算过程放在素数表上,将乘除法变成素数指数的加减法,这样就会避免计算的结果其实很小但是中间过程就爆掉数据类型的情况。

      应用1:大型组合数的求解(uva 10375).

      已知C(m,n) = m!/(n!(m-n)!),现在给出p、q、r、s(p≥q,r≥s,p、q、r、s≤10000),计算C(p,q)/C(r,s)。输出结果不超过100000000,保留五位小数。

      分析:计算组合数时间上没有太大问题,最终的输出结果也不算太大,但是这里如果分别求分母和分子的组合数,考察p、q、r、s的范围,计算10000!是会爆掉c++语言中任何一个数据类型的,因此这里考虑利用分解定理,将待求计算式分解到2~10000的素数表上。

     

      参考代码如下:

     

    #include<stdio.h>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    const int N = 10001;
    using namespace std;
    bool isprime[N];
    int prime[N],nprime;
    int e[N];
    
    void doprime()  //埃拉托色尼筛选法  prime[1]~prime[nprime]记录[1,N]区间的所有素数
    {
         long long i , j;
         nprime = 0;
         memset(isprime,true,sizeof(isprime));
         isprime[1] = 0;
           for(i = 2;i < N;i++)
           {
                  if(isprime[i])
                  {
                        prime[++nprime] = i;
                        for(j = i+i;j < N ;j += i)
                        {
                            isprime[j] = false;
                        }
                  }
           }
    }
    
    void add_integer(int n , int d)   //对整数n进行素数分解,指数存在e[]中,参数d取得正负1用来表示分子和分母的阶乘数。
    {
         for(int i = 1;i <= nprime;i++)
         {
              while(n % prime[i] == 0)
              {
                  n /= prime[i];
                  e[i] += d;
              }
              if(n == 1)  break;
         }
    }
    
    void add_factorial(int n , int d)   //将n的阶乘素数分解结果存储在e[]当中,参数d区别该数在分数线上的位置.
    {
         for(int i = 1;i <= n;i++)
              add_integer(i , d);
    }
    int main()
    {
        doprime();
    
        //for(int i = 1;i <= nprime  ;i++)
              //printf("%d ",prime[i]);
            int p , q , r , s;
            while(scanf("%d%d%d%d",&p , &q , &r , &s) != EOF)
            {
    
                memset(e , 0 , sizeof(e));
                   add_factorial(p , 1);
                   add_factorial(s , 1);
    
                   add_factorial(r , -1);
                   add_factorial(q , -1);
    
                   add_factorial(p-q , -1);
                   add_factorial(r-s ,  1);
    
                   double ans = 1.0;
    
                   for(int i = 1;i <= nprime;i++)
                       ans *= pow(prime[i] , e[i]);
    
                   printf("%.5lf\n",ans);
            }
    }

     

     

     

      应用2:一个基于素数分解的最优化问题(uva 10791)

      给出一个整数n,n最大可取2^31-1.求得一个长度至少为2的序列,使得这个序列的最小公倍数是n,且在所有满足这个条件的序列中,该序列的元素之和是最小的。求出这个最小元素之和。

     

      分析:这里要讨论一个序列的最小公倍数,凭空构造非常麻烦,因此这里联想到唯一分解定理,我们基于整数n在素数表上的分解,构造一个满足“序列上各元素的最小公倍数是n”这个条件,然后再去考虑如何满足“序列元素之和最小”这个条件。

     

       

       

      但是这个问题分析到这里还是不够,因为对于n=1,n只有一个因子的时候,为了满足题设“序列的长度不得小于2”的限制条件,需要进行做出特殊处理。

      

      基于这些分析,便可以进行编码实现了。

       

      简单的参考代码如下:

     

    #include<stdio.h>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    
    using namespace std;
    
    long long prime_resolve(long long n)
    {
         long long ans = 0;
         for(int i = 2;i <= sqrt(n)+1;i++)
         {
             long long temp = 1;
              while(n % i == 0)
              {
                  n /= i;
                  temp *= i;
              }
             if(temp != 1)
              ans += temp;
              if(n == 1)  break;
         }
        if(n != 1)
         return ans+n;
        else
         return ans;
    }
    
    
    int main()
    {
    
    
    
            long long n;
            int tt = 1;
            while(scanf("%lld",&n) && n)
            {
                 printf("Case %d: ",tt++);
    
                   long long num = prime_resolve(n);
    
    
                   if(n == 1)         printf("2\n");
                   else if(n == num)  printf("%lld\n",num+1);
                   else               printf("%lld\n",num);
    
            }
    }

     

    转载于:https://www.cnblogs.com/rhythmic/p/5846558.html

    展开全文
  • 初等数论及其应用 第五版 Kenneth H.Rosen著 夏鸿刚译 含书签,方便查阅。加州伯克利大学经典教材 中文版阅读无压力。。
  • 初等数论及其应用》第一章 整数 1.1 数和序列 本节主要介绍了数集合、整数序列的概念。 数 良序性质 每个非空的正整数集合都有一个最小元。 良序性质可以作为定义正整数集合的公理,或者由一组公理推导出来...

    《初等数论及其应用》第一章 整数(1)

    1.1 数和序列

    本节主要介绍了数集合、整数序列的概念。

    良序性质

    每个非空的正整数集合都有一个最小元。
    良序性质可以作为定义正整数集合的公理,或者由一组公理推导出来。我们说正整数集合是良序的,但是所有整数的集合不是良序的,因为在有些整数集合中没有最小的元素,如负整数的集合,小于100的偶数集合和全体整数的集合。

    有理数与无理数

    定义:
    如果存在整数p和q≠0,使得r=p/q,则称实数r是有理数。如果r不是有理的,则称为无理数。

    例1.1 -22/7,0=0/1,2/17和1111/41都是有理数。

    定理1.1:
    √2 是无理数。

    代数数与超越数

    定义:
    数α称为代数数,如果它是整系数多项式的根;也就是说,α是代数数,如果存在整数a0,…,an使得anαn+an-1αn-1+……+a0=0.如果数α不是代数数,称之为超越数。

    例1.2无理数 √2 是代数数,因为它是多项式x2-2=0的根。

    最大整数函数

    最大整数

    定义:
    实数x的最大整数记为[x],是小于或等于x的最大整数,即[x]是满足[x]≤x[x]+1的整数。

    例1.3 [5/2]=2 ,[-5/2]=-3 ,[Π]=3 ,[-2]=-2 ,[0]=0 .
    注记 最大整数函数也被称为取整函数。除此之外,还有上取整函数。

    例1.4如果n是整数,则对于任意实数x,都有[x+n]=[x]+n。

    定义:
    实数x的分数部分记为{x},是x于[x]的差,即{x}=x-[x]。
    由于[x]≤x<[x]+1,从而对任意实数x,0≤{x}=x-[x]<1,因为x=[x]+{x},所以x的最大取整也叫做x的取整数部分。

    例1.5{5/4}=5/4-[5/4] = 5/4-1 =1/4. {-2/3} = -2/3-[-2/3] = -2/3-(-1) = 1/3.

    丢番图逼近

    鸽笼原理

    定理1.2:
    如果把k+1或者更多的物体放入k个盒子中,那么至少有一个盒子中有两个或者更多的物体。

    狄利克雷逼近定理

    定理1.3:
    如果α是一个实数,n是一个正整数,则存在整数a和b,1≤a≤n,使得| aα - b | < 1/n。

    例1.6假定α=√2 且 n=6.
    我们发现1 × √2 ≈ 1.414 ,2 × √2 ≈ 2.828 ,3 × √2 ≈ 4.243 ,4 × √2 ≈ 5.657 ,5 × √2 ≈ 7.071 ,6 × √2 ≈ 8.485 .在这些数中,5 × √2的分数部分最小。我们看到 | 5 × √2 - 7 | ≈ | 7.071 - 7 | = 0.071 ≤ 1/6. 所以如果 α = √2 ,n = 6,那么我们可以取 a = 5,b = 7,从而使得 |aα - b | < 1/n。

    序列{ an }是一列数a1,a2,a3,… 。序列中的项可以用映射f(i) = ai跟正整数集合建立起一一映射。

    等比数列

    定义:
    等比数列是形式为a,ar,ar2,ar3,…的序列,其中初始项a和公比r都是实数。
    注:数论中的一个常见问题是如何寻找构造序列的通项公式或者规则,即使仅有很少的几项是已知的(例如寻找第n个三角数1+2+3+…+n的公式)。尽管一个序列的几个初始项不能决定这个序列,但是知道前几项有助于我们猜测通项公式或者规则。

    等差数列

    定义:
    等差数列即为形式为a,a+d,a+2d,…,a+nd,…的序列。

    例1.7猜测an的公式,这里序列{an}的前八项是5,11,29,83,245,731,2189,6563.
    我们注意到每一项都接近前一项的3倍,暗示着在an的通项公式中有项3n。对于n=1,2,3,…,整数3n分别为3,9,27,81,243,729,2187,6561.比较这两个序列,我们会发现产生这个序列的公式为an=3n+2。

    例1.8猜测an的公式,这里序列{an}的前10项是1,1,2,3,5,8,13,21,34,55.从不同的角度观察这个序列,我们注意到这个序列中前两项之后的每一项都是它之前两项的和。也就是说,我们发现an=an-1+an-2,3≤n≤10.这是一个递归定义序列的例子,将在1.3节讨论。在这个例子中列出的项时斐波那契数列的前几项,这个序列将在1.4节中讨论。

    可数与不可数

    定义:
    一个集合可数,如果它是有限的或者是无穷的但与正整数集合之间存在一个一一映射。如果一个集合不是可数的,则称为不可数。

    一个无穷集合时可数的当且仅当其中的元素可以排成一个由正整数标记的序列。为了看到这一点,只要注意从正整数集合到一个集合S的一一映射f其实就是把集合在的元素列成序列a1,a2,…,an,…,其中ai=f(i).

    例1.9整数集合是可数的,因为整数可以被列出来,由0开始,接下来是1和-1,2和-2,如此继续下去,这样产生一个序列0,1,-1,2,-2,3,-3,…,这里a1=0,a2n=n,a2n+1=-n,n=1,2,…。

    定理1.4:
    有理数集合是可数的。

    展开全文
  • Lucas定理用于解决较大组合数的取模问题,下面的理论整理源自冯志刚的《初等数论》,其与百度百科上呈现的Lucas定理形式上不同,但是容易看到二者的转化形式。 首先我们来整理一下冯志刚的《初等数论》中关于...

    Lucas定理用于解决较大组合数的取模问题,下面的理论整理源自冯志刚的《初等数论》,其与百度百科上呈现的Lucas定理形式上不同,但是容易看到二者的转化形式。

     

    首先我们来整理一下冯志刚的《初等数论》中关于Lucas定理的证明:

    转载于:https://www.cnblogs.com/rhythmic/p/7287180.html

    展开全文
  • 数论无疑是数学中十分重要的学科,读这本书让你体会数论的魅力。
  • 0 积分下载;文件大小:1.75 M;本书是Kenneth.H.Rosen所著《Elementary Number Theory(5ed)》一书的习题详解,是英文的。
  • 欧几里得是数论当中最基本的定理,以其为基础的拓展欧几里得算法在解决同余方程、求模逆元等问题。 首先来介绍几个概念,数论当中一些基本的概念其实在小学就学过,但是很长一段时间并没有用到它们,因此这里再...

      欧几里得是数论当中最基本的定理,以其为基础的拓展欧几里得算法在解决同余方程、求模逆元等问题。

     

      首先来介绍几个概念,数论当中一些基本的概念其实在小学就学过,但是很长一段时间并没有用到它们,因此这里再拿出来温习一下。

      我们常常用a|b来表示b能够整除a(b > a),即b/a是整数,但是“|”在使用的过程中容易和绝对值、几何定义符、条件概率混淆,所以,这里我们用a\b来表示a能够整除b。

     

      约数:如果b\a,则称b是a的约数。

      倍数:如果b\a,则称a是b的倍数。

      最大公约数:gcd(a,b) = max{k | k\a 且k\b}。

      最小公倍数:lcm(a,b) = min{k | k>0 , a\k 且b\k}

     

      那么现在我们面临一个重要的问题,给出一系列数字,我们想要通过一个程序得到这些数字的最大公约数或者最小公倍数, 应该怎么做呢?

      容易想到穷举,当然,容易想到的代价是牺牲大量的时间,我们需要用更好的思维去简化这个过程。

     

      计算最大公约数的方法:欧几里得算法.

      n>m,gcd(m,n) = gcd(n % m, m) , gcd(0,n) = n.

      证明:

      n = qm + r,r>0。
      我们假设存在这样一个d,它是m、n的公因子,即d\a 且 d\b。

      可以看到r = n - qm ,假如c = xa + yb,且d\a,d\b,那么d\c。这里是同样道理,所以d\r,加上之前的d\b,定理成立.


        

       基于这个结论,我们在求解gcd(m,n)(n > m)的时候,可以转而去求gcd(n % m , m).

      求gcd(n % m , m)的时候,可以转而去求gcd(m%(n%m) , n%m)

      ……

      这就形成了一个递归性质的求解过程,可能在说这个递归的流程你就会质疑,上面的证明过程我们给出的公因子相同,但是如何保证其是最大公因子(最大公约数)呢?想象一下这个递归过程,如果保证了递归的最后一层得到的公因子d是最大公因数,那么最终我们就会返回一个最大公约数。

    那么现在我们要解决的一个主要问题变成了:递归的最底层是什么呢?或者说,递推到什么程度开始“归”呢?想象一下,递推下去的终点,gcd(a,b)的a、b中必然有一个数是0,然后用我们在定理中定义的:gcd(a,0) = a.a其实就是整个递归过程中的解,这保证了递归过程中传递的约数一直是最大公约数。

    而在设计递归程序的时候,为了得到返回值(即上一段的a),我们规定gcd(a,b)函数a>b,这样返回结果即为:gcd(a,0),返回a.

     参考代码如下:

    #include<cstdlib>
    
    #include<iostream>
    
    using namespace std;
    
    long long gcd(int a , int b)
    
    {
    
         if(b == 0)
    
              return a;
    
         else  return gcd(b , a%b);
    
    }

     

      以欧几里得算法为基础进行拓展,得到的拓展欧几里得算法能够帮助我们解决更多的问题,尤其是模方程问题。

     

     

     

       基于上面的推导,我们就可以编程来实现这样一个求解二元一次方程ax+by=gcd(x,y)的一个特解了,参考代码如下:

     

     //ax + by = gcd(a,b),函数返回值为gcd(a,b)
    long long extend_gcd(long long a , long long b, long long &x , long long &y)
    {
         if(a == 0 && b == 0)  return -1;
         if(b == 0){x = 1 , y = 0;return a;}
         long long d = extend_gcd(b,a%b,y,x);
         y -= a/b*x;
         return d;
    } 

     

     

      拓展欧几里得算法一个重要应用就是求剩余系下的逆元.

                         

      与矩阵逆元类似,我们先去讨论逆元的存在性,再去解决如何求解逆元.

      

     

      计算方法:

      承接对逆元存在性的分析

      考察而原方程ax+my=1

      利用拓展欧几里得算法计算x(需要保证在m剩余系下)

      简单的参考代码如下:

     

    //ax = 1(mod n),返回x,即为a在n下的逆元
    long long mod_reverse(long long a , long long n)
    {
        long long x , y;
        long long d = extend_gcd(a,n,x,y);
        if(d == 1)  return (x%n+n)%n;
        else        return -1;
    }

     

    转载于:https://www.cnblogs.com/rhythmic/p/5875436.html

    展开全文
  •  应用4:阶乘的欧拉函数值(uva 11440)。  给出整数n , m,n∈[2,10^7],n≥m≥1,n-m≤10^5.那么请问[2,N!]有多少个x满足下列的性质,x的所有素因子都大于M.  分析:      参考代码如下:   #...
  • 复数的相关概念性质详解 以下内容摘自 我的博客:算法竞赛中的数论问题 - 数论全家桶(信奥 / 数竞 / ACM)作者孟繁宇,四万字,十三万字符的竞赛数论完全总结,将会择机发布,敬请期待 ~
  • 费马小定理在化简数论问题有着广泛用途。 转载于:https://www.cnblogs.com/rhythmic/p/5928369.html
  • 在线性代数中,我们用高斯消元解决多元的线性方程组,而在数论中,面对一元变量的线性模方程组,我们利用中国剩余定理去求解x。 转载于:https://www.cnblogs.com/rhythmic/p/5928483.html...
  •      化到这一步,我们就将原来一个... 单纯说矩阵快速幂也没有太大的难度,我们直接结合矩阵快速幂的一个非常有用的应用来讲。       转载于:https://www.cnblogs.com/rhythmic/p/5915399.html
  • 数和序列 良序性质 每个非空的正整数集合都有一个最小元 所有整数的集合不是良序的。 有理数 可以被写为整数的比的数的集合(若存在整数p,q ≠ 0,使得r = p / q,则称实数r为有理数) 代数数 ...
  • 二次剩余详解 以下内容摘自 我的博客:算法竞赛中的数论问题 - 数论全家桶(信奥 / 数竞 / ACM)作者孟繁宇,四万字,十三万字符的竞赛数论完全总结,将会择机发布,敬请期待 ~
  • 【学习笔记】高斯整数(全部相关概念及例题详解)
  • ACM初等数论

    2016-11-27 15:23:59
    这篇博客简要总结一下,ACM中的一些初等数论问题,包括euler phi函数,中国剩余定理,,euler phi函数ϕ(n)=n∏ki=1(1−1pi)\...证明详见《初等数论及其应用》int euler_phi(int n) { int ans = n; for(int i=2 ; i*i
  • 转自:... 学习总结:初等数论(3)——原根、指标及其应用 2016-05-19 15:58:28|分类:信息学——学习总|标签:初等数论数学|举报|字号订阅 学习总...
  • 吴正尧老师 初等数论 第三周 关于同余的笔记
  • 【转载】学习总结:初等数论(3)——原根、指标及其应用 写得太好了。。忍不住转载啊。。 未授权,侵权删。 原博文链接:...
  • 数论,顾名思义是将数...初等数论和其他离散数学分支一样,在计算机科学、信息安全(密码学)、离散控制系统和代数编码等许多领域有着广泛的应用。这篇文章,将介绍关于数在整除性方面的一些基础的问题。有关整除的一...

空空如也

空空如也

1 2 3 4
收藏数 65
精华内容 26
关键字:

初等数论及其应用