5.4 acwing数学知识部分 质数 约数

872. 最大公约数

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定 nn 对正整数 ai,biai,bi，请你求出每对数的最大公约数。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数对 ai,biai,bi。

输出格式

输出共 nn 行，每行输出一个整数对的最大公约数。

数据范围

1≤n≤1051≤n≤105,
1≤ai,bi≤2×1091≤ai,bi≤2×109

输入样例：

2
3 6
4 6

输出样例：

3
2

 思路：由欧几里得算法，（a,b）和（b，a%b）同余，当b余到最后为0时，无论什么数取0的余数都是它本身。对该递归的证明：

a可以表示成a = kb + r（a，b，k，r皆为正整数，且r

假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。

而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r

因此d也是b,a mod b的公约数。

因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。

代码：

#include
using namespace std;
#include
#include
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout< 
2. 
869. 试除法求约数
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定 nn 个正整数 aiai，对于每个整数 aiai，请你按照从小到大的顺序输出它的所有约数。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个整数 aiai。
 
输出格式
 
输出共 nn 行，其中第 ii 行输出第 ii 个整数 aiai 的所有约数。
 
数据范围
 
1≤n≤1001≤n≤100,
 2≤ai≤2×1092≤ai≤2×109
 
输入样例：
 
2
6
8
 
输出样例：
 
1 2 3 6 
1 2 4 8 
 
思路：把该数的约数和约数对应的另一个约数都加入即可
 
#include
using namespace std;
#include

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        vectora;
        int m;
        cin>>m;
        for(int i=1;i<=m/i;i++)
        {
            if(m%i==0)
            {
                a.push_back(i);
                if(i!=m/i)a.push_back(m/i);//注意避免重复
            }
        }
        sort(a.begin(),a.end());
        for(auto x:a)cout< 
 3. 
870. 约数个数
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定 nn 个正整数 aiai，请你输出这些数的乘积的约数个数，答案对 109+7109+7 取模。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个整数 aiai。
 
输出格式
 
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7109+7 取模。
 
数据范围
 
1≤n≤1001≤n≤100,
 1≤ai≤2×1091≤ai≤2×109
 
输入样例：
 
3
2
6
8
 
输出样例：
 
12
 
思路：首先，将每个数的质因数分解的结果放在hash中，has[5]=2,表示5的平方。然后，再根据上图公式计算约数个数和即可。
 
#include
using namespace std;
#include
const int N=1e9+7;

int main()
{
    int n;
    cin>>n;
    unordered_maphash;
    while(n--)
    {
        int m;
        cin>>m;
        for(int i=2;i<=m/i;i++)
        {
            while(m%i==0)
            {
                m/=i;
                hash[i]++;
            }
            
        }
        if(m>1)hash[m]++;
    }
    long long res=1;
    for(auto x:hash)res=res*(x.second+1)%N;
    cout< 
 4. 
871. 约数之和
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定 nn 个正整数 aiai，请你输出这些数的乘积的约数之和，答案对 109+7109+7 取模。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个整数 aiai。
 
输出格式
 
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+7109+7 取模。
 
数据范围
 
1≤n≤1001≤n≤100,
 1≤ai≤2×1091≤ai≤2×109
 
输入样例：
 
3
2
6
8
 
输出样例：
 
252
 
思路：思路同上，根据公式完成
 
#include
using namespace std;
const int N=1e9+7;
int main()
{
    int n;
    cin>>n;
    unordered_maphash;
    while(n--)//这些步骤都同上
    {
        int m;
        cin>>m;
        for(int i=2;i<=m/i;i++)
        {
            while(m%i==0)
            {
                m/=i;
                hash[i]++;
            }
        }
        if(m>1)hash[m]++;
    }
    long long res=1;
    for(auto x:hash)
    {
        long long t=1;
        for(long long i=1;i<=x.second;i++)
        {
            t=(t*x.first+1)%N;//注意加上括号，这里修改过
        }
        res=res*t%N;
    }
    cout< 
二、质数 
  
 
 
 5. 
866. 试除法判定质数
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定 nn 个正整数 aiai，判定每个数是否是质数。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个正整数 aiai。
 
输出格式
 
共 nn 行，其中第 ii 行输出第 ii 个正整数 aiai 是否为质数，是则输出 Yes，否则输出 No。
 
数据范围
 
1≤n≤1001≤n≤100,
 1≤ai≤231−11≤ai≤231−1
 
输入样例：
 
2
2
6
 
输出样例：
 
Yes
No
 
思路：如图
 
#include
using namespace std;
bool pd(int n)
{
    if(n==1)return false;
    if(n==2)return true;
    for(int i=2;i<=n/i;i++)//i<=n/i的判定条件因为i一开始从左向右，当他到达根号n时，右边的对应指针不可能再向左移动，应为已经被i走过了
    {
        if(n%i==0)return false;
        
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int m;
        cin>>m;
        if(pd(m))cout<<"Yes"< 
 6. 
867. 分解质因数
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定 nn 个正整数 aiai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
 
输入格式
 
第一行包含整数 nn。
 
接下来 nn 行，每行包含一个正整数 aiai。
 
输出格式
 
对于每个正整数 aiai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
 
每个正整数的质因数全部输出完毕后，输出一个空行。
 
数据范围
 
1≤n≤1001≤n≤100,
 2≤ai≤2×1092≤ai≤2×109
 
输入样例：
 
2
6
8
 
输出样例：
 
2 1
3 1

2 3
 
思路：如图
 
#include
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int m;
        cin>>m;
        for(int i=2;i<=m/i;i++)
        {
            if(m%i==0)
            {
                int s=0;
                while(m%i==0)//把i作为质因数除尽，计算后面时就可以除去前面的质因数的影响
                {
                    m/=i;
                    s++;//该质因数有多少个
                }
                cout<1)cout<1，那么说明没有除尽，那么最后一个m就是他的最大质因数
        cout< 
 7. 
868. 筛质数
 
   题目
   提交记录
   讨论
   题解
   视频讲解
 
给定一个正整数 nn，请你求出 1∼n1∼n 中质数的个数。
 
输入格式
 
共一行，包含整数 nn。
 
输出格式
 
共一行，包含一个整数，表示 1∼n1∼n 中质数的个数。
 
数据范围
 
1≤n≤1061≤n≤106
 
输入样例：
 
8
 
输出样例：
 
4
 
第一种解法：暴力解
 
void get_primes2(){
    for(int i=2;i<=n;i++){

        if(!st[i]) primes[cnt++]=i;//把素数存起来
        for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
}
 
 第二种算法：埃式筛法
 
void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}
 
第三种：线性筛法
 
思路：如图
 
#include
using namespace std;
#include
#include
const int N=10010
bool st[N];
int ss[N],cnt;
void saichu(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])ss[cnt++]=i;//先把素数存起来
        for(int j=0;ss[j]>n;
    saichu(n);
    cout<