数论总结1(基础数论)
一.进位计数制
1.进制表示:
表示b进制下的n+1位数。
2.进制转换:
进制向十进制转换:
乘以基数并展开:
十进制向b进制转换:
整数部分除以基数并倒取余数。
小数部分乘以基数,并顺取整数部分
3.例题:
a.天平1:
一个天平,有N个重量未知的砝码,砝码重量可由你自由确定。
砝码可任意放在天平的左右两边,但要求称出从1到M之间所有的重量,
现给出\(N\)的值,请问M最大值为多少。
答案:\([0,3^N]\)。具体见下面解析。
b.天平2:
一个天平,砝码分别为1g、3g、9g、27g、…、6561g…,
每个砝码只有一个,要称重的物品放在天平的左侧,而砝码允许放在天平的左右两侧。
已知一个物品的质量N (N≤108 ),问如何称重?
_____________________________________________________________________
解析:
就是将\(N\)转换成三进制后,
将三进制中的0、1、2三个状态转换成 0、1 、-1
具体的说,就是0和1不变,2变成-1后,其高一位加1。
例如:
\(N\)转化为三进制后为{1,2,0,1} , 那么对应的状态为:{1,-1,-1,0,1}。
即三进制中的2是没法直接称量的,因为每个重量的砝码只有一个,所以只能通过相减来处理。
c.天平3:
一个天平,砝码分别为1g、3g、9g、27g、…、6561g…,每个砝码只有一个,
要称重的物品放在天平的左侧,而砝码只允许放在天平的右侧。
将由这个系统可以称出来的重量按从小到大的顺序进行排列,
得到下列序列:1,3,4,9,10,...。问其中的第K个重量是多少?
_____________________________________________________________________
解析:仔细观察就可以发现,将K转化为二进制后,为1的即放置对应质量的三进制重量砝码即可。
二.素数和合数
1.素数判定:
枚举\(\sqrt{N}\)内的质因子即可。 时间复杂度\(O(\sqrt{N})\)。
2.欧拉筛法(线性筛素数)
原理:每个合数必有一个最小素因子,用这个因子筛掉合数。
实现代码(筛出\([0,N]\)的素数):
void Prime(int N){ memset(isPrime,true,sizeof(isPrime)); isPrime[0 ] = false ; isPrime[1] = false ; for (int i = 2 ; i <= N ; i++){ if ( isPrime[i] )prime[++ total] = i ; //把素数记录下来 //遍历已知素数表中比i的最小素因数小的素数,并筛去合数 for(int j = 1 ; j <= total && i * prime[j] <= N ; j++){ isPrime[ i * prime[j] ] = false ; if (!( i % prime[j])) break; //找到i的最小素因数 } } }