一.进位计数制

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