数论总结1(基础数论)

一.进位计数制

1.进制表示:

数论总结1(基础数论)

表示b进制下的n+1位数。

2.进制转换:

进制向十进制转换:
乘以基数并展开:
数论总结1(基础数论)

十进制向b进制转换:
整数部分除以基数并倒取余数。
小数部分乘以基数,并顺取整数部分
数论总结1(基础数论)

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的最小素因数
             }
      }
}