Fork me on GitHub

数论基础

发表于 | 分类于
字数统计: 2,501字 | 阅读时长 ≈ 10分钟

傻逼选手数论屁也不会

基本概念及代码

质数

质数也称素数,即恰好包含两个不同因子的整数.（好智障啊）
1 不是质数.
判断单个数是否为质数.
如下.

1
2
3
4
5
6
7
8
bool is_prime(int x)
{
	if (x <= 1) return 0;
	if (x == 2) return 1;
	for (int i = 2; i <= sqrt(x+0.5); i++) //用Sqrt(x+0.5)防止精度失真
	if (x % i == 0) return 0;
	return 1;
}

每次的时间复杂度为 O(sqrt(n)).

但是对于很N个数的质数表单个判断就很无力,因为同一个数的因数会被重复地判断

比如4被2筛去,但6还要再次被筛一遍.

所以就诞生了Euler大师的能保证每个数只被筛到一次的线性筛,能做到O(n).

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
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 1e7+10;
bool is_prime[Maxn];
int prime[Maxn],cnt = 0;
void Euler_Prime(int s)
{
	memset(is_prime,1,sizeof(is_prime));
	is_prime[1] = 0; //1 不是质数. 
	for (int i = 2; i <= s; i++)
	{
		if (!is_prime[i]) prime[++cnt] = i;
		for (int j = 1; j <= cnt && i * prime[j] <= s; j++)
		{
			is_prime[prime[j] * i] = 0;
			if (i % prime[j] == 0) break;//确保了每个合数只被他最小的质因数筛去.6啊
		}
	}
}
int main(int argc, char *argv[])
{
	Euler_Prime(Maxn);
	int x;
	scanf("%d",&x);
	printf("%d\n",is_prime[x]);
	return 0;
}

Euclid算法.

最简单的是欧氏的辗转相除求最大公约数(gcd)的方法.

1
2
3
4
int gcd(int x,int y)
{
	return (y == 0) ? x : gcd(y,x%y);
}

会不会爆栈呢?不会,可以证明,gcd的递归层数不超过4.785lgN + 1.6723(紫书P311)

对于任意的x,y,有lcm(x,y) gcd(x,y) = xy; 证明略请自行百度

Extended Euclid算法

找出一对整数x,y要求能够使得ax+by = gcd(a,b) 且使得|x| +|y|尽可能的小.

1
2
3
4
5
6
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
	if(!b){d = a;x = 1;y = 0;} 
	//如果b = 0，那么就是ax = d，令x = 1,y = 0即可
	else {ex_gcd(b,a%b,d,y,x) y-=x*(a/b);} 
}

欧拉phi φ函数

公式如下

单个欧拉函数可以这样求:

1
2
3
4
5
6
7
8
9
10
11
12
int euler_phi(int n)
{
	int m = sqrt(n+0.5);
	int ans = 0;
	for (int i = 2; i <= m; i++)
	if (n % i == 0)
	{
		ans = ans * (i-1)/i;
		while(n % i == 0) n /= i; 
	} 
	return ans;
}

以Euler的质数筛 可以类比算出欧拉函数,时间复杂度也为O(n).

1
2
3
4
5
6
7
8
9
10
11
12
void phi_table(int n)
{
	for (int i = 2; i <= n; i++) phi[i] = 0;
	phi[1] = 1;
	for (int i = 2; i <= n; i++) if (!phi[i])
		for(int j = i; j <= n; j+=i)
		{
			if (!phi[j])
			phi[j] = j;
			phi[j] = phi[j] / i * (i-1); 
		}
}

中国剩余定理（孙子定理）

问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

说明白一点就是说，存在一个数x，除以3余2，除以5余三，除以7余二，然后求这个数。上面给出了解法。再明白这个解法的原理之前，需要先知道一下两个定理。

定理1：几个数相加，如果存在一个加数，不能被数a整除，那么它们的和，就不能被整数a整除。

定理2：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。

现给出求解该问题的具体步骤：

1、求出最小公倍数

lcm=357=105

2、求各个数所对应的基础数

（1）105÷3=35

35÷3=11……2 //基础数35

（2）105÷5=21

21÷5=4……1

定理2把1扩大3倍得到3，那么被除数也扩大3倍，得到21 * 3=63//基础数63

3、105÷7=15

15÷7=2……1

定理2把1扩大2倍得到2，那么被除数也扩大2倍，得到15 * 2=30//基础数30

把得到的基础数加和（注意：基础数不一定就是正数）

35+63+30=128

4、减去最小公倍数lcm（在比最小公倍数大的情况下）

x=128-105=23

那么满足题意得最小的数就是23了。一共有四个步骤。下面详细解释每一步的原因。

（1）最小公倍数就不用解释了，跳过（记住，这里讨论的都是两两互质的情况）

（2）观察求每个数对应的基础数时候的步骤，比如第一个。105÷3=35。显然这个35是除了当前这个数不能整除以外都能够被其他数整除，就是其他数的最小公倍数。相当于找到了最小的开始值，用它去除以3发现正好余2。那么这个基础数就是35。记住35的特征，可以整除其他数但是不能被3整除，并且余数是2。体现的还不够明显，再看下5对应的基础数。21是其他数的最小公倍数，但是不能被5整除，用21除以5得到的余数是1，而要求的数除以5应该是余1的。所以余数被扩大，就得到了相应的基础数63。记住这个数的特征，可以被其他数整除但是被5除应该余三。同理，我们得到了第三个基础数23，那么他的特征就是：可以被其他数整除，但是不能被7整除，并且余数为2。

（3）第三步基础数加和，为什么要这样做呢？利用就是上面提到的定理1。

35+63+30=128。对于3来说，可以把63+30的和看作一个整体，应该他们都可以被3整除。看着上面写出的三个数的特征，运用定理1来说，就是在35的基础上加上一个可以被3整除的倍数，那么得到的结果依然还是满足原先的性质的，就是128除以同样还是余2的。同理，对于5还说，这个数被除之后会剩余3；对于7来说，被除之后剩余2。所以说，我们当前得到的这个数是满足题目要求的一个数。但是这个数是不是最小的，那就不一定了。

（4）应该不能确定是不是最小的数，这个时候就要用到他们的最小公倍数了。最小公倍数顾名思义，一定是一个同时被几个数整除的最小的一个数，所以减去它剩余下来的余数还是符合题意要求的。当然也同样可以运用定理1来解释，只不过是加法变成了减法，道理还是一样的。当然具体要不要剪还是要看和lcm的大小关系的。

稍微的总结一下：就是已知m1,m2,m3是两两互质的正整数，求最小的正整数x，使它被m1,m2,m3除所得的余数分别是c1,c2,c3。孙子定理的思想便是线分别求出被其中数mi整除余1而被两外两个数整除的数Mi(i=1,2,3)，则所求数之一的便是c1M1+c2M2+c3M3。由此我们可以得到n个两两互质数的情况。证明上面已经一步一步给出。

那么，到此为止基本的中国剩余定理的内容我们以及了解了，包括解答方法。那么如何编码呢？按照上面这个思路去编码，其实并不难。一共分为四大步。但是，大多数人的困惑在于如何求取基础数。这里呢，提供两种方法：

（1）第一种就是一直递增，直到找到。例如：3的基础数，35是其他数的最小公倍数。那么就从35开始，一直自增，知道余数为2，便停止（利用while循环）。

（2）第二种方法呢就是辗转相除法上得来的。这里的例子体现的不够明显，应当看看去求取乘法逆元的过程，下面讲的内容和乘法逆元有很大的关系，所以还是看看的好。简单举个例子：

假设现在三个数分别是14，3，5，它们两两互质，且要求的数除以5余3。求5对应的基础数。有：

42÷5=8……2

5÷2=2……1

所以1=5 - 2 2=5 - 2 （42- 8 5 ）=-2 42+17 * 5

那么-2 42=-84 17 5=85 -84+85=1

把1扩大3倍变成3，则有-84 * 3=-252也就是5对应的基础数。

第一点： 基础数可以是负数，这个之前点到过。//并且下面的解法就是有这样的。

第二点： 当得到余数为1的时候后面的算式相当于是一个回溯的过程，最后解到-2 * 42。 但是还只不过是余数是1的情况对应的数，再运用定理2我们就得到了-252这个基础数。实际上要是看过乘法逆元，这里实际就是乘法逆元的求解过程，而-2也就是42关于15取模的乘法逆元。

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
#include<bits/stdc++.h> 
#define ll long long
using namespace std;
//扩展欧几里得算法 
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b){d=a;x=1,y=0;}
    else
	{	
        exgcd(b,a%b,d,y,x);
        y-=(a/b)*x;
    }
}
//中国剩余定理 
ll China(int n,ll *m,ll *a)
{
    ll M=1,d,y,x=0;
    for(int i=0;i<n;i++) M*=m[i];
    for(int i=0;i<n;i++)
	{
        ll w=M/m[i];
        gcd(m[i],w,d,d,y);
        x=(x+y*w*a[i])%M;
    }
    return (x+M)%M;
}
ll m[15],a[15];
int main(int argc, char *argv[])
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&m[i],&a[i]);
    printf("%lld",China(n,m,a));
}

题目传送门
UVa-11426
UVa-11582
UVa-10375
UVa-10791

Last edited - 2018-02-08 karriganasta ❤