猫史档案馆

 

 

快速幂

 

 

快速幂，顾名思义就是快速求一个数的幂。

幂的运算就不在这里讲了吧？不会的补一补初一数学（开玩笑）

 

好吧，当然会讲的。下面的图片截自我的博客（所有图片都来自我的博客）：

 

于是我们回过头来再来看：

 

 

 

通过上面的幂的运算，我们不难发现：

 

 

因此，我们的代码也就写出来了。

int Kuaisumi(int a,int b,int n){
    int ans=1;
    while(b){
        if(b%2)ans=ans*a%n;
        a=a*a/n
        b/=2;
    }
    return ans;
}

 

 

同余问题

 

 

 

 

剩余系

 

剩余系是指模正整数 n 的余数所组成的集合。

如果一个剩余系中包含了这个正整数 n 所有可能的余数，那么就被称为是模 n 的一个完全剩余系，记作

 

而简化剩余系就是完全剩余系中与 n 互素的数，记作

 

更一般地，

 

一般地，对于任意正整数 n，有 n 个余数： 0,1,2,...,n-1

 

 

性质

 

 

对于整数a,b,c和自然数m,n，对模m同余具有以下性质。

 

 

 

 

运算方法

 

 

 

 

 

 

约数问题

 

 

 

两个数的最大公约数是指这两个数共有的约数中最大的一个，记作

 

两个数中除0以外最小的一个共有的数就叫做这两个整数的最小公倍数。

 

 

话说回来，如何求最大公约数？

 

 

辗转相减

 

• 辗转相减即即尼考曼彻斯法，又称更相减损术。

• 用大数减小数，以所得的差和原先的小数重新相减，不断重复上述过程，知道两数相等，即为最大公约数。

 

//辗转相减求两个数的最大公约数
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b;
    for(int i=1;i<=a;i++)
        if((a%i==0)&&(b%i==0)) c=i;
    cout<<c<<endl;
    return 0;
}

 

当然这代码当然是TLE。怎么优化？

（优化评测机）

 

 

 

辗转相除

 

 

• 辗转相除法，又称欧几里得算法

运用了下面这个原理：

 

函数如下

int 喵(int x,int y){
    return y==0?x:喵(y,x%y);
}

 

有欧几里得算法自然有扩展欧几里得算法。但是比较复杂，为了保持此帖的简单易懂，先略过，在（二）会讲。

 

 

素数问题

简单地说，素数筛问题就是让你求一个区间内的素数。

 

有如下几种类型:

1.求素数个数

2.求第k个素数

等等。

 

 

原始解法

 

我们有一种极为喵的解法，O(n^2)。

枚举每个数，从2开始枚举每个小于此数的数。如果这个数是外层枚举的那个数的约数，表示外层枚举的数是合数，打上标记。

#i喵lude<bits/stdc++.h>
using namespace std;
int i,j,k,n,a[1000005],prime[1000005],cnt,q;
int main(){
	cin>>n>>q;
	for(i=2;i<n;i++)
		for(j=2;j<i;j++)
			if(!(i%j))a[i]=1;
	for(i=2;i<n;i++)
		if(!a[i]){
            cnt++;prime[cnt]=i;
        }
    while(q--){cin>>k;cout<<prime[k]<<endl;}
	return 0;
}

这代码绝对妥妥的T了~

怎么办？问题出在哪里？

（评测机）

当然不是。

 

考虑优化：对于任意一个正整数n，必然有小于sqrt(n)（根号n）的约数。

因此，只需枚举j，只需要到j*j<=i就行了。

#i喵lude<bits/stdc++.h>
using namespace std;
int i,j,k,n,a[1000005],prime[1000005],cnt,q;
int main(){
	cin>>n>>q;
	for(i=2;i<n;i++)
		for(j=2;j*j<=i;j++)
			if(!(i%j))a[i]=1;
	for(i=2;i<n;i++)
		if(!a[i]){
            cnt++;prime[cnt]=i;
        }
    while(q--){cin>>k;cout<<prime[k]<<endl;}
	return 0;
}

结果呢？还是TLE。（一盆冷水）

问题出在哪？

（评测机）

 

因此，我们需要使用——筛法

 

 

 

Eratosthenes 筛

 

 

这个筛法也是很原始的。

从2 开始，将每个数的各个倍数，标记成合数。

范围内所有未被标记的数，就是所求的全部素数。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
for (int i = 2; i <= n; i++)
    for (int j = i+i; j <= n; j+=i)
        isPrime [j] = false ;

然而这个代码还需要很多优化！（两盆冷水）

 

考虑优化：任一合数都是某个质数的倍数

所以只需要用质数去筛即可。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
    for (int i = 2; i <= n; i++)
        if ( isPrime [i]) {
            for (int j = i+i; j <= n; j+=i)
        isPrime [j] = false ;
    }

 

容易知道复杂度是

虽然很难证明，但是

 

 

很显然，这个代码仍然需要很多优化。

 

事实上一个n 以内的数若是合数，必然有不大于sqrt(n)的约数. 且若发现一个质数p，也不应该从2 * p 开始筛起，应该从p * p 筛起，因为更小的合数已经被别的质数筛掉了。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
    for (int i = 2; i*i <= n; i++)
        if ( isPrime [i]) {
            for (int j = i*i; j <= n; j+=i)
                isPrime [j] = false ;
        }

 

 

这个代码已经很优秀了。但是不幸的是，还有更好的方法。

 

这就需要用到

Euler 筛（线性筛）

 

 

之前的筛法，一个合数会被筛去多次（被它的每个质因数筛一次）

如果我们能保证每个合数只被筛一次，就能得到时间复杂度为线性的筛法。

Euler 筛就是这样的筛法，它保证每个合数只被其最小质因数筛去。

for (int i = 2; i <= n; i++) {
    if ( isPrime [i]) prime . push_back (i);
        for (int j = 0; j < prime .size (); j++) {
            if (i * prime [j] > N) break ;
            isPrime [i * prime [j]] = false ;
            if (i % prime [j] == 0) break ;
        }
}

 

 

当然每次被最大的质因数筛掉也是可以的：

for(int i=2;i<=n;i++)
{
	if(!check[i])prime[cnt++]=i;//若当前数i没有被之前的所有数筛掉，表明i是素数，将i添加进素数表prime
	for(int j=0;j<cnt&&i*prime[j]<100000001;j++)//注意i*prime[j]不要超过n的上限（10^8）
	{
		check[i*prime[j]]=1;//将当前素数prime[j]的i倍标记为合数
		if(i%prime[j]==0)break;//关键步骤：保证每个合数只被筛一次
	}
}

 

恭喜你，这个算法可以算是比较优的了。

 

 

 

积性函数

 

 

 

放一张我的博客上的截图：

 

 

求法概述

 

 

 

 

 

欧拉函数

 

 

欧拉函数是小于或等于n的正整数中与n互质的数的数目，记作 φ(n)。

属于积性函数的一种。

 

 

性质

 

 

 

 

因此，求欧拉函数的代码也就很容易写出来了。

 

#include<bits/stdc++.h>
using namespace std;
int n,olhs[40005],prime[40005],tot,ans;
bool flag[40005]
void getolhs(){//求欧拉函数
    int i,j;
    olhs[1]=1;//定义
    for(i=2;i<=40000;i++){
        if(!flag[i]){//判断是否为素数
            prime[++tot]=i;//列入素数表
            olhs[i]=i-1;//性质1
        }
        for(j=1;j<=tot;j++){
            if(i*prime[j]>N)break;//越界了直接跳
            flag[i*prime[j]]=1;//表示i*prime[j]不是素数
            if(i%prime[j]==0{
                olhs[i*prime[j]]=olhs[i]*prime[j];
                //利用欧拉函数的积性，性质3
                break;
            }
            else olhs[i*prime[j]]=olhs[i]*(prime[j]-1);
            //性质3
        }
    }
}
int main(){
    getolhs();
    return 0;
}

 

 

OK，今天就讲到这里。