数学(三):gcd,lcm,一次函数与素数筛

DragonL9 · 2024-07-11 22:39:02 · 个人记录

引言：

函数与数论是数学学科中的主要模块，也是信息学奥赛考察的重点内容。本文将介绍有关数论与一次函数的相关内容。

在进入正题以前，让我们来看一道有关质因数分解的题目。

附加题：P1069 [NOIP2009 普及组] 细胞分裂

根据题目要求，只有培养后细菌的总数能被试管数M整除才能完成培养，而M=m_1 ^{m_2}。因此，我们可以将m1分解质因数。对于每一种细胞a[i],随着时间的推移，细胞数量呈指数级增长。若a[i]^n能被M的所有质因子整除，且a[i]^n的幂次大于等于M的质因子的幂次时，a[i]^n能被M整除。此时，可以完成一次培养，这次培养所需要的时间便是a[i]^n中含有该质因子的个数除以M中该质因子的幂次。最后，这种细菌培养所需的时间是对于M的所有质因子的培养所需时间的最大值。输出的答案只需取对每种细菌培养时间的最小值即可。

代码如下：

/*
    一个整数能被M整除，说明能平均分
    最后的细胞总数量是M的倍数(细胞总数%M==0)
    0s:s[i];1s:s[i]^2;2s:s[i]^3;3s:s[i]^4;...
    s[i]^?|M 
    (p1^k1*p2^k2*...*pm^km)^?=s[i]^? 
    =>p1^(k1*?)*p2^(k2*?)*...*pm^(km*?) 
    M=q1^f1*q2^f2*...*qw^fw 
    添加幂次，不修改底数(质因子的数量)
    如果s[i]^?能被M整除
    1.M的所有质因子全部在s[i]中出现过,s[i]能把M所有的质因子整除 
    2.默认满足：M的对应质因子幂次小于 s[i]的质因子幂次 
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
struct nums{
    int prime;//质因子
    int cnt; //个数 
}p[N];
int a[N];
int m1,m2;//底数，幂次
int n;
int total=0; 
void div(int num){
    if(num==1){
        return;//特判 
    }
    for(int i=2;i*i<=num;i++){//O(sqrt(n))
        if(num%i==0){
            p[++total].prime=i;//存储当前的质因子 
            while(num%i==0){
                num/=i;
                p[total].cnt++;
            }
            p[total].cnt*=m2;//默认需要乘m2 
        }
    }
    if(num!=1){
        p[++total].prime=num;
        p[total].cnt=m2;
    }
    return;
}
bool check(int x){
    for(int i=1;i<=total;i++){
        if((x%p[i].prime)) return 0;
    }
    return 1;
}
int minn=INT_MAX;
/*
    第0s,都是1个
    第1s,p1这个质因子幂次为tmp
    第2s,p1这个质因子的幂次为2*tmp
    (tmp>=p[i].cnt) 
*/
void cultivate(int x){
    int maxx=0;//基础培育时间最小值是0 
    for(int i=1;i<=total;i++){//m1质因子的种类 
        int tmp=0;
        while(x%p[i].prime==0){
            tmp++;
            x/=p[i].prime;
        }
        int ans=(p[i].cnt-1)/tmp+1;//向上取整 
        maxx=max(maxx,ans);
    }
    minn=min(minn,maxx);
    return;
}
signed main(){
    cin>>n;
    cin>>m1>>m2;
    div(m1);//分解质因数 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(check(a[i])==0){//检查一开始是否就不存在对应的质因子 
            continue;
        }
        cultivate(a[i]);//能继续说明值得继续培养 
    }
    if(minn==INT_MAX) cout<<-1;
    else cout<<minn;
    return 0;
}

第一部分：gcd和lcm

gcd(最大公约数)与lcm(最小公倍数)是信息学奥赛中的主要内容之一。两者存在以下关系：

lcm(a,b)=ab \div gcd(a,b)

我们可以简单地举例验证一下。例如，当a=4，b=6时，易得两者的最小公倍数为12。我们先求出gcd(4,6)=2，则

对于c++中gcd的求解，我们可以使用如下的代码： ```cpp int gcd(int a,int b){ if(a%b==0)return b; else return gcd(b,a%b); } ``` 或者使用c++自带的库函数：__gcd(a,b); 如果两个数的gcd为1，则称这两个数为互质数，互质数的最小公倍数为两数之积。下面来看一道例题。 ## 例题：[P5436 【XR-2】缘分](https://www.luogu.com.cn/problem/P5436) 根据题目要求，我们要求出在区间[1,x]之间的两个整数的lcm的最大值。由上文可知，两个互质数的lcm为两数的乘积，我们便很容易能想到使两个正整数分别为$x$和$(x-1)$，两者的lcm为$x \times (x-1)$，这个值便是所求答案。注意：当x=1时，答案应为1，此时需特殊判断。代码如下： ```cpp #include<bits/stdc++.h> using namespace std; long long n; int t; int main(){ cin>>t; while(t--){ cin>>n; if(n==1) cout<<1<<endl; else cout<<n*(n-1)<<endl; } } ``` # 第二部分：一次函数一次函数是初高中阶段最基本的初等函数之一，其图像为一条直线。一次函数的一般形式为： $y=kx+b (k\ne0)$，其中，k称为斜率，b称为截距。对于任意一条直线y=kx+b，设它的倾斜角为∠A，直线上有任意两点$(x_1,y_1),(x_2,y_2)$，则有： $k=tan(A)=\frac {abs(y1-y2)} {abs(x1-x2)}

b=\frac {y_1 \times x_2 - y_2 \times x_1}{x_2 - x_1}

推导过程如下图所示：

我们还能将一次函数y=kx+b看作一个等差数列，其中b为首项，k为公差，x为项数。

下面来看一道例题。

例题：P2026 求一次函数解析式

本题是典型的求函数的解析式问题，可以直接利用上文求斜率和截距的公式进行求解。注意：当求k或b时答案非整数时，应当将分子和分母同时除以它们的最大公约数，以达到约分的目的。注意分情况输出解析式。代码如下：

#include<bits/stdc++.h>
using namespace std;
int x1,yy,x2,y2;
int k,b;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    cin>>x1>>yy>>x2>>y2;
    cout<<"y=";
    int xt=x1-x2,yt=yy-y2;
    if((double)yt/xt<0){
        cout<<"-";
        xt=abs(xt);yt=abs(yt);
    }
    if(yt%xt!=0){
        int t=gcd(xt,yt);
        xt/=t,yt/=t;

        cout<<yt<<"/"<<xt<<"*";
    }
    else cout<<yt/xt;
    cout<<"x";
    int xb=yy*x2-x1*y2;
    int yb=x2-x1;
    if(xb==0) return 0;
    if((double)xb/yb<0){
        cout<<"-";
        xb=abs(xb);yb=abs(yb);
    }
    else cout<<"+";
    if(xb%yb==0){
        cout<<xb/yb;
    }
    else{
        int tt=gcd(xb,yb);
        xb/=tt,yb/=tt;
        cout<<xb<<"/"<<yb;
    }
    return 0;
}

第三部分：埃氏素数筛法

对于素数筛，我们有如下的朴素方法：

bool prime(int x){
if(x<=1)return false;
for(int i=2;i*i<=x;i++){
if(x%i==0) return false;
}
return true;
}

对于求一个数是否为素数，上述方法的复杂度为O(\sqrt(n))，批量处理的复杂度为O(m\sqrt(n))

接下来介绍一种效率较高的筛法：埃氏筛法。其基本原理是：当我们找到一个素数，其所有的倍数都是合数。例如，2是质数，而4，6，8，10，……是2的倍数，并且它们都是合数。因此，埃氏筛法在找到一个素数（即没有做标记的数）时会将其所有的倍数（均为合数）做标记，避免重复筛选。其算法复杂度为O(nk)

算法实现如下：

bool vis[N];
int prime[N];
void E(){
    vis[0]=vis[1]=1;
    for(int i=1;i<=N;i++){
     if(!vis[i]){
        for(int j=i*2;j<=N;j+=i)vis[j]=true;
     }                  
   }
    return;
}

下面来看两道例题。

例题1：B3969 [GESP202403 五级] B-smooth 数

本题要求求出给定数的最大质因子。我们可以对埃氏筛法进行改进。每当我们发现一个素数，便将它和它的倍数的最大质因子标记为它本身。在往后搜查的过程中，每当一个数发现了比当前质因子更大的质因子时，原质因子将被新值覆盖。由于质数以单调递增的顺序排列，当我们筛取完毕时对每一个数存下的质因子便是其最大的质因子。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int vis[N+10];
int prime[N+10],id=1;
void E(){
    vis[0]=vis[1]=1;//特判0,1都不是 
    for(int i=2;i<=N;i++){
        if(!vis[i]){//合数的所有倍数一定是该合数的质因子的倍数 
            for(int j=i;j<=N;j+=i){
                vis[j]=i;
            }
        }
    }
}
int n,b;

int main(){
    cin>>n>>b;
    E();
    int ans=0;
    for(int i=2;i<=n;i++){
        if(vis[i]<=b) ans++;
    }
    cout<<ans+1;
    return 0;
}

例题2：P6421 [COCI2008-2009#2] RESETO

本题要求出被删除的第k个数。基于埃氏筛法，我们可以在标记的过程中累加计数器。当计数器的值为k时输出对应数即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
bool vis[N+50];
int cnt=0;
int n,k;
void E(){
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            cnt++;
            if(cnt==k){
                cout<<i<<endl;
                exit(0);
            }
            for(int j=i+i;j<=n;j+=i){
                if(!vis[j]){
                    cnt++;
                    if(cnt==k){
                        cout<<j<<endl;
                        exit(0);
                    }   
                }
                vis[j]=1;

            }
        }
    }
}
int main(){
    cin>>n>>k;
    E();
    return 0;
}

结语：

本文介绍的相关数学知识都是该学科的基础性内容，也是信息学中的重要内容。对于每一位竞赛选手，这些都是必须熟练掌握的知识内容。