发表于

河南理工大学第三次公开课

图片

素数

什么是质数

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

基本思想找质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h> // 万能头文件

using namespace std;

int main() {
	
	int n ;
	scanf("%d",&n) ;
	
	if( n == 1 ) {
		printf("false") ;
		return 0;
	}

	for (int i = 2 ; i <= n - 1; i ++ ) {
		if ( n % i == 0 ) {
			printf("fasle") ;
			return 0;
		}
	}
	
	printf("true") ;
	
	return 0;
}

万能头文件

时间小优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int main() {
	int t ; scanf("%d",&t) ;
	
	if ( t == 1 ) {
		printf("false") ;
		return 0;
	}
	
	for (int i = 2 ; i * i <= t ; i ++ ) {
		if ( t % i == 0 ) {
			printf("false") ;
			return 0;
		}
	}
	
	printf("true") ;
	return 0;
}

但是上面两种方法有个很大的弊病，就是不能一次筛出很多素数，加入我们要筛出(1~1e5)之间的所有素数，上面两种方法就很慢了，时间复杂度是O(n^2)

普通筛——埃拉托斯特尼(Eratosthenes)筛法

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 50 ;

bool prime[maxn] ;

void init() {
	memset(prime ,true ,sizeof(prime)) ;
	prime[1] = prime[0] = false ;
	for (int i = 2 ; i < maxn ; i ++ ) {
		for (int j = 1 ; i * j < maxn ; j ++ ) {
			prime[i*j] = false ;
		}
	}
}

int main() {
	init() ;
	int t ; scanf("%d",&t) ;
	printf("%d\n",prime[t] ) ;
	
	return 0;
}

例题

大神筛法–欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool IsPrime[1000010];  
int Prim[1000010];  
int  euler_prime(int n){  
    int num = 0, j;  
    for(int i = 2; i <= n; i ++){  
        if(!IsPrime[i])  
            Prim[num ++] = i;  
        for(j  = 0; j < num; j ++){  
            if(i * Prim[j] > n)  
                break;  
            IsPrime[i * Prim[j]] = true;  
            if(i % Prim[j] == 0)  
                break;  
        }  
    }  
}/*欧拉筛*/

图片

扩展

算术基本定理

快速幂

求 a^b 朴素算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;

int main() {
	int a ,b ,res = 1 ;
	
	scanf("%d %d",&a ,&b) ;
	
	for (int i = 1 ; i <= b ; i ++ ) {
		res = res * a ;
	}
	
	printf("%d\n",res) ;
	
	return 0;
}

当b为1e9的时候在1s的时间内程序是远远计算不出来的，因此我们需要改进算法
例如5^10 , 10 的二进制表示为 1010

5^10 = 5^(2^2+2^8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
const ll mod = 1e9 + 7 ;

ll ksm(ll a ,ll b ) {
	ll res = 1 ;
	while ( b ) {
		if ( b & 1 ) res = res * a % mod ;
		b >>= 1 ;
		a = a * a ;
	}
	return res ;
}

int main() {
	
	printf("%lld\n",ksm(2 ,100 )) ;
	return 0;
}

时间复杂度O(n*lgn)

模

费马小定理

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

逆元

大佬博客

当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有bc≡1(mod m)；
则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);
即a/b的模等于ab的逆元的模；

费马小定理+快速幂求逆元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
const int maxn = 1e5 + 50 ;
const int mod = 1e9 + 7 ;

ll ksm(ll a ,ll b ) {
	ll res = 1 ;
	while ( b ) {
		if ( b & 1 ) res = res * a % mod ;
		b >>= 1 ;
		a = a * a % mod ;
	}
	return res ;
}

ll inv(ll s) {
	return ksm(s ,mod-2 );
}

int main() {
	ll t ; scanf("%lld",&t) ;
	printf("%lld\n",inv(t) ) ;
	
	return 0;
}

利用逆元求组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll ;
const ll mod = 1e9 + 7 ;
const int maxn = 1e6 + 50 ;

ll fac[maxn] ;

void init() {
    fac[1] = 1 ;
    for (int i = 2 ; i < maxn ; i ++ ) {
        fac[i] = (fac[i-1] * i) % mod ;
    }
}

ll ksm(ll a,ll b) {
    a %= mod ;
    ll res = 1 ;
    while(b) {
        if ( b ) res = (res * a) % mod ;
        b /= 2 ;
        a = (a * a ) % mod ;
    }
    return res ;
}

ll inv(ll a) {
    return ksm(a ,mod - 2) ;
}

ll C(ll n ,ll m ) {
    return fac[n] * inv(fac[n-m]) % mod * inv(fac[m]) % mod ;
}


int main() {
	
	return 0 ; 
}

扩展gcd求组合数

扩展gcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll ;
const ll mod = 1e9 + 7 ;
const int maxn = 1e6 + 50 ;

ll fac[maxn] ;

void init() {
    fac[1] = 1 ;
    for (int i = 2 ; i < maxn ; i ++ ) {
        fac[i] = (fac[i-1] * i) % mod ;
    }
}

//利用扩展gcd求逆元 
ll ex_gcd(ll a ,ll b ,ll &x ,ll &y ){
	if( b == 0 ){
		x = 1 ;
		y = 0 ;
		return a ;
	}
	int ans = ex_gcd(b ,a%b ,y ,x );
	y -=  x * (a / b);
	return ans;
}

ll inv(ll n){
	ll x ,y ;
	ex_gcd(n ,mod ,x ,y );
	x = (x % mod + mod ) % mod ;
	return x ;
}

ll C(ll n ,ll m ) {
	return fac[n] * inv(fac[n-m]) % mod * inv(fac[m]) % mod ;
}

int main() {
	
	return 0 ; 
}

扩展

卢卡斯定理

图片

发表于 | 分类于

这是最近学习Java的一点心得，解释都写在代码里面里面了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package test;

public class Main {

//  (1.
//	public static void main(String[] args) {
//		System.out.println("Hello World");
//	}
	
// (2.
//	public Main(String name){
//	   //这个构造器仅有一个参数：name
//	   System.out.println("小狗的名字是 : " + name ); 
//	}
//	public static void main(String []args){
//	   // 下面的语句将创建一个Puppy对象
//		Main myPuppy = new Main( "tommy" );
//	}
	
// (3.	
//	int b = 6 ; //相当于全局的一个东西
//	static int c = 5 ; //被创建到了public Main之中，只有Main对象才可以调用，其他对象调用不了
//	public Main() { //类变量
//		System.out.println(b);
//		
//	}
//	public void sayHello() {
//		int d = 9 ; //成员变量结束后销毁
//		System.out.println(d) ;
//		System.out.println("Hello World") ;
//	}
//	public static void main(String[] args) {
//		Main myMain = new Main() ;
//		myMain.sayHello();
//		System.out.println(myMain.b) ;
//		System.out.println(myMain.c) ;
//		int a = 5 ;
//		System.out.println(a) ;
//	}
}

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于

Welcome to shemplle’s backups

1
I want this place be a free , random platform

图片

图片