Acwing 第四章 数学知识

一、质数

866. 试除法判定质数

#include
#include
#include

using namespace std;
const int N = 105;

bool isprime(int x)
{
    if(x<2) return false;
    for(int i=2;i<=x/i;i++) //用i<=x/i多快好省，用sqrt(x)很慢，用i*i<=x可能爆int
    {
        if(x%i==0) return false;
    }
    return true;
}

int main()
{
    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        if(isprime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

867. 分解质因数

#include
#include
#include

using namespace std;

void depart(int x)
{
    for(int i=2;i<=x/i;i++) //n中最多只含有一个大于sqrt(n)的因子
    //对其进行优化,先考虑比sqrt(n)小的
    {
        if(x%i==0) //i一定是质数
        {
            int s=0;
            while(x%i==0)
            {
                x = x/i;
                s++;
            }
            cout< 1) cout<1，说明这就是大于sqrt(n)的唯一质因子
    puts("");
}

int main()
{
    int n,x;
    cin>>n;
    while(n--)
    {
        cin>>x;
        depart(x);
    }
    return 0;
}

线形筛素数法(埃筛法)

868. 筛质数

#include
#include
#include

using namespace std;

const int N = 1e6+10;
int n;
int prime[N],cnt; //素数数组及其个数
bool st[N]; //是否被筛除

void get_primes(int n) //埃式筛法
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
            for(int j=i*2;j<=n;j+=i) //只将所有质数的倍数筛去
            {
                st[j] = true;
            }
        }
    }
}
void get_primes(int n) //线性法
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j=0;prime[j] <= n/i;j++)
        {
            st[prime[j]*i] = true;
            if(i % prime[j] == 0) break; //prime[j]一定是i的最小质因子
        }
    }
}
int main()
{
    cin>>n;
    get_primes(n);
    cout<

二、约数

869. 试除法求约数

#include
#include
#include

using namespace std;
const int M = 105;
int n,x;
vectordivisior(int x)
{
    vectorres;
    for(int i=1;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res.push_back(i);
            if(x/i != i) res.push_back(x/i); //当遇到i为x的根号时，只能输出一次约数
        }
    }
    sort(res.begin(),res.end());//题目要求结果有序
    return res;
}

int main()
{
    cin>>n;
    while(n--)
    {
        cin>>x;
        vector v = divisior(x);
        for(auto t:v)
        {
            cout<

870. 约数个数


思路：对于每个因数，指数从0到α-1共α个供选择构成约数，故得到公式

#include
#include
#include
using namespace std;
const int M = 2e9+10,MOD = 1e9+7;
unordered_mapprimes; //用哈希表来存储所有质因数的指数
int n,x;
typedef long long LL; //答案非常大，用LL存储
void get_cnt(int x)
{
    for(int i=2;i<=x/i;i++) //求x的质因数及其指数
    {
        while(x%i==0)
        {
            primes[i]++;
            x = x/i;
        }
    }
    if(x>1) primes[x]++; //大于sqrt(x)的质因数
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>x;
        get_cnt(x);
    }
    LL res = 1;
    for(auto k:primes)
    {
        res = (res * (k.second+1)) % MOD ; //注意：每次乘完都需要取余
    }
    cout<

871. 约数之和

#include
#include
#include

using namespace std;
typedef long long LL;
const int N = 2e9+10,MOD = 1e9+7;
unordered_mapprimes;//用哈希表存储质因数及其指数
int n,x;

void get_primes(int x)//求质因数及其指数
{
    for(int i=2;i<=x/i;i++)
    {
        while(x%i==0)
        {
            primes[i]++;
            x = x/i;
        }
    }
    if(x>1) primes[x]++;//处理大于sqrt(x)的质因数
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>x;
        get_primes(x);
    }
    LL res = 1;
    for(auto prime:primes)
    {
        LL tmp = 1;
        int p = prime.first;//质因数
        int e = prime.second;//指数
        while(e--)//注意循环次数为e，不是e-1
        {
            tmp = (tmp * p + 1) % MOD; // p^0 + p^1 +……+p^e秦九韶算法，注意要取模
        }
        res = (res * tmp) % MOD;//注意每次运算对答案也取模
    }
    cout<

872. 最大公约数

#include
using namespace std;
typedef long long LL;
int n;
int a,b;
int gcd(int a,int b)
{
   return b==0?a:gcd(b,a%b); 
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        cout<

三、欧拉函数

定义

873. 欧拉函数

#include
#include
#include

using namespace std;

int n,x;

int main()
{
    cin>>n;
    while(n--)
    {
        cin>>x;
        int res = x;
        for(int i=2;i<=x/i;i++)
        {
            if(x%i==0)//i是x的一个质因数
            {
                res = (res / i) * (i-1); //先除法后乘法，防止溢出
                while(x%i==0)//除干净
                {
                    x = x/i;
                }
            }
        }
        if(x>1) res = (res/x) *(x-1);//先除法后乘法，防止溢出
        cout<

874. 筛法求欧拉函数

#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 1e6+10;
int primes[N],cnt;
int phi[N];
bool st[N];

LL get_eulers(int n)
{
    phi[1] = 1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i-1;
        }
        for(int j=0;primes[j] <= n/i;j++)
        {
            st[primes[j]*i] = true;
            if(i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    LL res = 0;
    for(int i = 1;i <= n;i++)
    {
        res += phi[i];
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    cout<

四、快速幂

875. 快速幂

#include 
#include 
#include 
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL a,k,p;

LL qmi(LL a,LL k,LL p) //a^k % p log(k)的时间内算出
{
    LL res = 1;
    while(k)
    {
        if(k&1) res = (LL)(res*a)%p;
        k >>= 1;
        a = (LL)(a * a) % p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while (n -- )
    {
        scanf("%lld%lld%lld", &a, &k,&p);
        cout<

876. 快速幂求逆元

a/b mod p 相当于 a*(power(a,p-2) mod p)

#include 
#include 
#include 

using namespace std;
typedef long long LL;

const int N = 1e5 + 10;

LL qmi(LL a,LL b,LL p)
{
    LL res = 1;
    while(b)
    {
        if(b&1) res = (LL)(res*a)%p;
        b >>= 1;
        a = (LL)a*a%p;
    }
    return res;
}

int n;
LL a,p;
int main()
{
   scanf("%d",&n);
   while(n--)
   {
       scanf("%lld%lld", &a, &p);
       LL t = qmi(a,p-2,p);
       if(a%p) cout<

五、扩展欧几里得

877. 扩展欧几里得算法


#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b * x;
    return d;
}
int n,a,b,x,y;
int main()
{
    scanf("%d", &n);
    while (n -- )
    {
        scanf("%d%d", &a, &b);
        exgcd(a,b,x,y);
        cout<
算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签

一品网 冀ICP备14022925号-6