听课总结

1. 质数

1.1 质数的判定------试除法

定义 : 在大于1的整数中,如果只包含1和本身这两个约数,则称其为质数
注意 : 所有小于等于1的整数既不是质数也不是合数.

#include<iostream>
using namespace std;
bool is_prime(int n)
{
    if (n<2) return false;
    for (int i=2;i<=n/i;i++)   
/*
因为因数都是成对出现的,所以我们只需要证明小的那个因数不成立
即可证明这对因数不成立
设n是除数,d是被除数,则d(小的那个因数)<=n/d(大的那个因数)
化简得d<=根号n,故只需要遍历到根号n即可
sqrt()会超时,i*i有越界风险,所以这里用n/i
*/
        if (n%i==0) return false;
    return true;
}
int main()
{
    int m;
    cin>>m;
    while(m--)
    {
        int n;
        cin>>n;
        if (is_prime(n)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

1.2 分解质因数------试除法(※)

质因数 : 指能整除给定正整数的质数
原理 : (算数基本定理)任何一个大于1的自然数N,如果N不为质数,
那么N可以唯一分解成有限个质数的乘积
即 N=p1^a1*p2^a2*...*pk^ak

#include <iostream>
using namespace std;
void divide(int x)
{
    for (int i=2;i<=x/i;i++)
/*
1.为什么直接遍历
一个数不能整除i,则他一定不能整除i的倍数,所以这里可以直接遍历
2.为什么i<=x/i
一个数只会有一个大于根号x的质因数,因为如果有两个,就比x还大了
所以这里i取到根号x就够了
*/
    if (x%i==0) 
    {
        int s=0;
        while(x%i==0) x/=i,s++;
        printf("%d %d\n",i,s);
    }
    if (x>1) printf("%d %d\n",x,1);
    //输出大于根号n的那个质因数
    cout<<endl;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        divide(x);
    }
    return 0;
}

1.3 质数筛(※)

1.朴素筛法
#include<iostream>
using namespace std;
const int N=1e7+10;
int primes[N],cnt;
bool st[N];
/*
primes[N] : 存储质数   cnt : 记录存储了几个质数
st[N] : 判断i有没有被筛过
*/
void get_primes (int n)
{
    for (int i=2;i<=n;i++)
    {
        if (!st[i]) primes[cnt++]=i;   //记录i为质数
        for (int j=i;j<=n;j+=i) st[j]=1;   //把i的倍数筛掉
    }
}
int main()
{
    int n;
    cin>>n;
    get_primes(n);
    cout<<cnt;
    return 0;
}
2.线性筛法
原理 : 
1.任何一个合数i都可以由最小质因子p*最大因数t得到,如果p不是质数,
就还能进行拆分,将拆分的部分给因数t,这样就又变成了最小质因数*最大因数
2.合数i的最小质因子p,也是i的倍数的最小质因子
所以当我们从小到大枚举质数,合数i能整除的第一个质数,必是其的最小质因子p
#include <iostream>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;   //用最小质因子把i的倍数筛掉
            if (i % primes[j] == 0) break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

2. 约数

2.1 试除法求约数(※)

原理 : 
1.约数(因数)成对出现,故只需要枚举较小的那个即可
2.如果两个约数不一样,则需在添加较大的那个约数(n/i)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> get_divisors (int x)
{
    vector<int> res;
    for (int i=1;i<=x/i;i++)
    {
        if (x%i==0)
        {
            res.push_back(i);   //先存较小的那个约数
            if (i!=x/i) res.push_back(x/i);  
            //如果两个约数不一样,再存较大的那个约数
        }
    }
    sort(res.begin(),res.end());   //从小到大排序
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        vector<int> res;
        res=get_divisors(x);
        for (int i=0;i<=res.size()-1;i++) cout<<res[i]<<" ";
        cout<<endl;
    }
    return 0;
}

2.2 求约数个数

原理 : 一个数的约数是由这个数的几个质因子相乘得到的
即 N = (p1^x1)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数
N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)
#include <iostream>
#include <unordered_map>
using namespace std;
const int N=1e9+7 ;
int main()
{
    int T; 
    cin>>T;
    unordered_map<int, int>primes;
    //unordered_map<键,值>变量名
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=2;i<=n/i;i++)
        {
            while(n%i==0)
            {
                primes[i]++;  
/*
当使用primes[i]++时，实际上是对键为i的值执行自增操作
如果键i在unordered_map中已经存在，则会将键为i的值加1
如果键i在unordered_map中不存在，会自动插入一个键为i
值为0的新键值对，并将值加1
*/
                n=n/i;
            }
        }
        if(n>1) primes[n]++;   //保存>根号n的那个质数
    }
    long long res=1;
    for(unordered_map<int,int>::iterator it=primes.begin();it!= primes.end();it++)
    //利用迭代器进行遍历,其中it是指向unordered_map的迭代器
    {
        res=res*(it->second+1)%N ;
        //it->second + 1表示对这个值部分进行加1的操作
    }
    cout<<res;
}

2.3 求约数之和

N的约数之和为 : (p1^0+p1^1+...p1^xk)*...*(pk^0+pk^1+...pk^xk)
#include <iostream>
#include <unordered_map>
using namespace std;
const int N=1e9+7 ;
int main()
{
    int T; 
    cin>>T;
    unordered_map<int, int>primes;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=2;i<=n/i;i++)
        {
            while(n%i==0)
            {
                primes[i]++;
                n=n/i;
            }
        }
        if(n>1) primes[n]++;
    }
    long long res=1;
    for(unordered_map<int, int>::iterator it=primes.begin();it!= primes.end();it++)
    //利用迭代器进行遍历
    {
        long long a=it->first,b=it->second;
        //a=当前的键,b=当前的值
        long long t=1;
        while(b--)
        {
            t=(t*a+1)%N;
        }
/*
循环1次之后 : t=a+1
循环2次之后 : t=a^2+a+1
循环b次之后 : t=a^b+a^b-1+...+1
*/
        res=res*t%N ;
    }
    cout<<res;
}

2.4 辗转相除法求最大公约数(※)

原理 : 用(a,b)表示a和b的最大公因数
则两个数的最大公约数,将其中一个数的倍数加到另一个数上
得到的新数,其公约数不变,比如(4,6)=(4+6x2,6)=(4,6+2×4)=2
即(a,b)=(a%b,b)=(b,a%b)
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        while(b)
        {
            int c=a%b;   //一直%,直到a%b=0
            a=b;
            b=c;
        }
        cout<<a<<endl;   //输出最大公约数a
    }
    return 0;
}

2.5 扩展欧几里得算法(※)

作用 : 用于求解方程 ax+by=gcd(a,b)的解
原理 : 
当 b=0时,ax+by=a,即 x=1,y=0
当 b≠0时,因为(a,b)=(b,a%b)
由此可以推出 : 
bx′+(a%b)y′=(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=(b,a%b)=(a,b)
即 x=y′,y=x′−⌊a/b⌋∗y′
(这里x′=原来的x,y′=原来的y)

#include <iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
    if (!b) x = 1, y = 0;   //如果b=0
    else
    {
        exgcd(b,a%b,y,x);   //这里已经x=y′,y=x′
        y-=a/b*x;
        //相当于y=x′−⌊a/b⌋∗y′
        /*
        exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        */
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

3. 欧拉函数
3.1 求某个数的欧拉函数

欧拉定理 : 若a与n互质,则a^ϕ(n)%n=1
1∼N中与N互质的数的个数被称为欧拉函数,记为ϕ(N)
原理 : 
(算数基本定理)任何一个大于1的自然数N,如果N不为质数,
那么N可以唯一分解成有限个质数的乘积即 N=p1^a1*p2^a2*...*pk^ak
因此ϕ(N)=ϕ(p1^a1)*ϕ(p2^a2)*...*ϕ(pk^ak)
对于任意一项ϕ(p^a),在1~p^a中与其不互质的数的个数为p^a-1个
[因为p的倍数与p^a皆为不互质关系,即有(1p,2p...(p^a-1)p)个]
所以ϕ(p^a)=p^a-p^a-1=p^a*(p-1/p)
结合上述三个等式可以得出 : ϕ(N)=N*(p1-1/p1)*(p2-1/p2)*...*(pk-1/pk)

#include <iostream>
using namespace std;
int phi(int x)
{
    int res=x;
    for (int i=2;i<=x/i;i++)   //找质因数
        if (x%i==0)
        {
            res=res/i*(i-1);
            /*
            相当于N*(p1-1/p1),第二次循环到这就是又乘了(p2-1/p2)
            ...以此类推
            */
            while (x%i==0) x/=i;
            /*
            因为是p1^a1,a1不一定是1,为了确保下一次是(p2-1/p2)
            这里要除到a1=1,把p1除尽
            */
        }
    if (x>1) res=res/x*(x-1);   //把>根号n的那个质数也除了
    return res;
}
int main()
{
    int n;
    cin>>n;
    while (n--)
    {
        int x;
        cin>>x;
        cout<<phi(x)<<endl;
    }
    return 0;
}

3.2 求1~N中所有数的欧拉函数

#include <iostream>
using namespace std;
const int N = 1000010;
int primes[N],cnt;
bool st[N];
int phi[N]; // 欧拉函数 Φ(x)
void get_eulers(int x)
{
    phi[1]=1;
    for (int i=2;i<=x;i++)
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            phi[i]=i-1;   //从1到质数i中与i互质的数个数为i-1
        }
        for (int j=0;primes[j]<=x/i;j++)
        {
            st[primes[j]*i]=true;
            if (i%primes[j]==0)
            {
/*
当p[j]是i的一个约数时,i的质因数与p[j]*i的质因数完全相同。
i=(p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^ap[j])...(pk^ak)
i*p[j]=(p1^a1)*(p2^a2)*(p3^a3)*...(p[j]^(ap[j]+1))...(pk^ak)
由欧拉函数的定义可知：
Φ(i)=i*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
Φ(i*p[j])=i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/p[j])*...(1-1/pk)
*/
                phi[i*primes[j]]=primes[j]*phi[i];
                break;
            }
/*
当i%p[j]!=0时，p[j]不是i的约数，i与i*p[j]的质因子相差一个p[j]
i=(p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)
i*p[j]=(p1^a1)*(p2^a2)*(p3^a3)*...(pk^ak)*(p[j]^a[j])
所以由欧拉函数的定义可知：
Φ(i)=i*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)
Φ(i*p[j])=i*p[j]*(1-1/p1)*(1-1/p2)*(1-1/p3)*...(1-1/pk)(1-1/p[j])
*/
            phi[i*primes[j]]=(primes[j]-1)*phi[i];
        }
    }
}
int main()
{
    int n;
    cin>>n;
    get_eulers(n);
    long long res=0;
    for (int i=1;i<=n;i++) res+=phi[i];
    cout<<res;
    return 0;
}

4. 快速幂

用处 : 快速的求出a^b%p的结果
原理 : 先预处理出(a^2^0至a^2^logb)%p的值,然后把b转换成二进制
用预处理的值表示出来
//(a*b)%p=(a%p)*(b%p)%p
#include <iostream>
using namespace std;
long long qmi(int a,int b,int p)
{
    long long res=1%p;
    while (b)   //这里的b是二进制
    {
        if (b&1) res=res*a%p;   //如果b的二进制表示的第0位为1,则乘上当前的a
        a=a*(long long)a%p; //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb}
        b>>=1;   //b右移1位
    }
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    while (n--)
    {
        int a,b,p;
        scanf("%d%d%d",&a,&b,&p);
        printf("%lld\n",qmi(a,b,p));
    }
    return 0;
}