【算法专项】数论初步

对于算法拖更了有一段时间，忙完期末也应该回归正轨了。这个寒假正确让自己的算法功底进一步提升，当然也要进行模拟训练，等1月中下旬的时候开始专题做蓝桥杯试题，现在有空的时候就学习一些算法，使自己的思维提高！

前言：数论是数学中比较有难度的部分，相信经历过高考的人也明白，特别体现在数列中。当然了，在算法竞赛中，数列常常以各种面貌出现，对数学思维非常高，本例通过数论初步有个整体了解，后期将会加大训练量。

• 唯一分解定理
• Eratosthenes筛选
• 扩展欧几里得算法
• 斐波那契求模（14年蓝桥杯A组）

题目1：给出除法表达式： X 1 / X 2 / X 3 / . . . / X k X_1/X_2/X_3/…/X_k X1​/X2​/X3​/…/Xk​，其中 X i X_i Xi​是整数。除法表达式应当按照从左到右的顺序求和，例如表达式 1 / 2 / 1 / 2 1/2/1/2 1/2/1/2的值为 1 / 4 1/4 1/4。但可以在表达式中嵌入括号以改变计算顺序，例如表达式 ( 1 / 2 ) / ( 1 / 2 ) (1/2)/(1/2) (1/2)/(1/2)的值为1。
输入X1,X2…Xk,判断是否可以通过添加括号使表达式为整数。K<=10000

输入:
4
1 2 1 2
3
1 2 3
输出:
1
0

分析：就是说表达式可以写成A/B的形式，很明显X2必须为分母，其他都可以，这就是最优的情况
E = X 1 / ( X 2 / X 3... X k ) = X 1 X 3 X 4... X k X 2 E=X1/(X2/X3...Xk)=frac{X1X3X4...Xk}{X2} E=X1/(X2/X3...Xk)=X2X1X3X4...Xk​
当然，我们已经将问题转换为：求（x1 * x3 * x4 * x5 … * xk)中的约数是否包含x2的全部约数。
如果就是简单想X1X3X4…Xk的话，时间复杂hen度过高而且也需要高精度运算。
这里讲述唯一分解定理。
将X2写成若干个素数相乘的形式，依次判断每个素数是否为分子的约数，到这里还是有一些疑惑，改怎么改进呢？很明显就是**每次约分Xi和X2的最大公约数gcd（Xi,X2)，**当且仅当X2变为1了，E为整数。
很明显，gcd使用辗转相除法了！

#include 

using namespace std;

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

int  judge(int x[],int k){
    x[2]/=gcd(x[1],x[2]);
    for(int i=3;i<=k;i++){
        x[2]/=gcd(x[i],x[2]);
    }
    return x[2]==1;
}

int main(){
    int k;
    while(cin>>k){
        int x[k+1];
        for(int i=1;i<=k;i++){
            cin>>x[i];
        }
        cout< 
Eratosthenes筛选 
 
 
题目2： 给出正整数n,m。区间[n,m]内 “无平方因子” 的数有多少个？？
 整数p无平方因子，当且仅当不存在k>1,使得p是k^2的倍数. 1<=n<=m<=10^12; n-n<=10^7
 
 
 
 
无平方因子数：是指其约数中，没有一个是平方数的正整数。简言之，将一个这样的数予以素因数分解后，所有素因数的幂都不会大于或等于2。例如：54=2333，由于54有约数9是平方数，所以54不是无平方数因数的数；而55=511,55没有约数是平方数，所以55是无平方数因数的数。
 
 
分析：简单的枚举必将超时，比较要判断10的7次方。很明显，这其实就是素数筛选了，我上次又在博客中写过。
 筛选的思想：对于不超过n的每个非负整数p，删除2p,3p,4p…处理完以后没有删除的就是素数。
 其中，素数定理非常重要：
 
     
      
       
        
         π
        
        
         (
        
        
         n
        
        
         )
        
        
         =
        
        
         −
        
        
         1
        
        
         +
        
        
         
          ∑
         
         
          
           k
          
          
           =
          
          
           1
          
         
         
          x
         
        
        
         
          ⌊
         
         
          
           
            cos
           
           
            ⁡
           
          
          
           2
          
         
         
          
           ⌊
          
          
           π
          
          
           
            
             (
            
            
             n
            
            
             −
            
            
             1
            
            
             )
            
            
             !
            
            
             +
            
            
             1
            
           
           
            n
           
          
          
           ⌋
          
         
         
          ⌋
         
        
       
       
         pi(n)=-1+sum_{k=1}^{x}leftlfloorcos ^{2}leftlfloorpi frac{(n-1) !+1}{n}rightrfloorrightrfloor 
       
      
     π(n)=−1+k=1∑x​⌊cos2⌊πn(n−1)!+1​⌋⌋
 

     
      
       
        
         
          
           lim
          
          
           ⁡
          
         
         
          
           x
          
          
           →
          
          
           ∞
          
         
        
        
         
          
           π
          
          
           (
          
          
           x
          
          
           )
          
         
         
          
           (
          
          
           
            x
           
           
            
             ln
            
            
             ⁡
            
            
             (
            
            
             x
            
            
             )
            
           
          
          
           )
          
         
        
        
         =
        
        
         1
        
       
       
         lim _{x rightarrow infty} frac{pi(x)}{left(frac{x}{ln (x)}right)}=1 
       
      
     x→∞lim​(ln(x)x​)π(x)​=1
 其中
     
      
       
        
         π
        
        
         (
        
        
         x
        
        
         )
        
       
       
         pi(x) 
       
      
     π(x)表示不超过x的素数个数。
 
#include 
#include 
#include

using namespace std;

const int maxn=100005;
int p[maxn];
int prim[maxn];
int len=0;

//筛选素数
void prime(int m){
    memset(p,0,sizeof(p));
    int k=sqrt(m+0.5);
    p[1]=1;
    for(int i=2;i<=k;i++){
        if(!p[i]){
            for(int j=i*i;j<=m;j+=i){
                p[j]=1;
            }
        }
    }
    len=0;
    for(int i=1;i<=m;i++){
        if(!p[i]){
            prim[len++]=i;
        }
    }
}

//平方因子
bool is_ping(int k){
    for(int i=0;i>n>>m;
    prime(m);
    for(int i=n;i<=m;i++){
        if(is_ping(i)) cnt++;
    }
    cout<<"n"< 
扩展欧几里得算法 
 
 
题目3：求直线ax+by+c=0有多少个整点(x,y).
 
 
很明显又是约分的问题了，这里对其进行扩展写法。
 
void gcd(int a,int b,int &d,int &x,int &y){
	if(!b){d=a;x=1;y=0;}
	else{gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
 
 
 
题目4：输入正整数a,n,m,输出a的n幂 mod m值
 
 
很明显，求幂，时间的度O(n),n很大必然不理想，有没有更快的方法呢？
 首先我们看看这个：
 
     
      
       
        
         
          a
         
         
          29
         
        
        
         =
        
        
         (
        
        
         
          a
         
         
          14
         
        
        
         
          )
         
         
          2
         
        
        
         ∗
        
        
         a
        
       
       
         a^{29} =(a^{14} )^{2}*a
       
      
     a29=(a14)2∗a
 
     
      
       
        
         
          a
         
         
          14
         
        
        
         =
        
        
         (
        
        
         
          a
         
         
          7
         
        
        
         
          )
         
         
          2
         
        
       
       
        a^{14}=(a^{7})^{2}
       
      
     a14=(a7)2
 
     
      
       
        
         
          a
         
         
          7
         
        
        
         =
        
        
         (
        
        
         
          a
         
         
          3
         
        
        
         
          )
         
         
          2
         
        
        
         ∗
        
        
         a
        
       
       
        a^{7}=(a^{3})^{2}*a
       
      
     a7=(a3)2∗a
 
     
      
       
        
         
          a
         
         
          3
         
        
        
         =
        
        
         
          a
         
         
          2
         
        
        
         ∗
        
        
         a
        
       
       
        a^{3}=a^{2}*a 
       
      
     a3=a2∗a
 可见一共做了7次乘法。
 
int pow_mod(int a,int n,int m){
	if(n==0) return 1;
	int x=pow_mod(a,n/2,m);
	long long ans=(long long)x*x%m;
	if(n%2==1) ans=ans*a%m;
	return (int ) ans;
}
 
斐波那契求模（14年蓝桥杯A组） 
说了那么多，我们再看一下一些应用实例。
 
 
 
2014年蓝桥杯A组题九：斐波那契数列大家都非常熟悉。它的定义是：
 
 
f(x) = 1 … (x=1,2)
 f(x) = f(x-1) + f(x-2) … (x> 2)
 
对于给定的整数 n 和 m，我们希望求出：
 f(1) + f(2) + … + f(n) 的值。但这个值可能非常大，所以我们把它对 f(m) 取模。
 但这个数字依然很大，所以需要再对 p 求模。
 

     
      
       
        
         
          (
         
         
          
           ∑
          
          
           
            i
           
           
            =
           
           
            1
           
          
          
           n
          
         
         
          f
         
         
          (
         
         
          i
         
         
          )
         
         
          )
         
         
        
         
          m
         
         
          o
         
         
          d
         
         
        
         f
        
        
         (
        
        
         m
        
        
         )
        
       
       
         left(sum_{i=1}^{n} f(i)right) bmod f(m) 
       
      
     (i=1∑n​f(i))modf(m)
 分析：其实拿到这个题的时候我心里咯噔了一下，这不就是快速幂吗？然而快速幂写起来还是非常麻烦的，这次我的代码也没有完全通过样例，后面我将会以快速幂为专题详细解答！
 
 
 
输入：
 输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
 输出：
 输出为1个整数，表示答案
 
 
 
 
样式输入：
 2 3 5
 样式输出：
 0
 
 
先将我的代码附上（时间超限），后期附上快速幂的写法：
 
#include 

using namespace std;

int main(){
    long long  n,m,p;
    cin>>n>>m>>p;
    long long a=1,b=1;
    if(m>=n+2){
        for(int i=3;i<=n+2;i++){
            long long t=a;
            a=b;
            b+=t;
        }
        cout<