一）逆元
即乘法逆元
说到逆元，基本上是为了求阶乘；之所以求阶乘，通常是为了求组合数；
数字极大时，一定需要一个MOD，这个MOD通常是100000……07之类的质数；
如果用通常的阶乘求法，非死不可；
使用扬辉三角，可以对付不少分，不过通常不是正解。
此时就需要用到逆元，或者说是乘法逆元，或者说是阶乘逆元，都是一个东西。

1）乘法逆元的定义性质：
每个数a均有唯一的与之对应的乘法逆元x，使得ax≡1(mod n)
一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

2）费马小定理
在模为素数p的情况下，有费马小定理 a^(p-1)≡1（mod p）
那么a^(p-2) * a≡1(mod p), 也就是说a的逆元为a^(p-2)


一）A/B hdu1576　逆元模板
要求(A/B) mod 9973，但由于A很大，我们只给出n(n=A mod 9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

八数码难题　P1379/BD358
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式
输入初始状态，一行九个数字，空格用0表示
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入 #1复制
283104765
输出 #1复制
4

奇偶性考察：
对于给定八数码棋局的初始状态，我们的目标是通过交换空格与其相邻棋子使棋盘达到目标状态。
其中，游戏规则是只能交换空格与其上下左右四个方向的相邻棋子。

假设棋局目标状态为如下形式：（A、B、C、D、E、F、G、H表示棋子）
 A  B  C
 D  E  F
 G  H         
而初始状态就是A、B、C、D、

一）优秀的拆分
一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1，10=1+2+3+4 等。
对于正整数 n 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，n 被分解为了若干个不同的 2 的正整数次幂。注意，一个数 x 能被表示成 2 的正整数次幂，当且仅当 x 能通过正整数个 2 相乘在一起得到。
例如，10=8+2=2^3+2^1是一个优秀的拆分。但是，7=4+2+1=2^2+2^1+2^0 就不是一个优秀的拆分，因为 1 不是 2 的正整数次幂。
现在，给定正整数 n，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。
输入格式
输入文件名为 power.in。
输入文件只有一行，一个正整数 n，代表需要判断的数。
输出格式
输出文件名为 power.out。
如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。
若不存在优秀的拆分，输出“-1”（不包含双引号）。
样例 1 输入
6
样例 1 输出
4 2
样例 1 解释
6=4+2=

一）单项选择題：
1)俺国的顶级域名，有点含糊，它实际上有两个.cn 和 .com.cn，这里的标准答案不如说是排除法，选(A)

2)2.二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（）。
A. 01 0010 1000 1011 B. 01 0010 1001 0011
C. 01 0010 1000 0001 D. 01 0010 1000 0011
这个不说了，答案就是解析；选（D）

3).一个32位整型变量占用（）个字节。
A. 32 B. 128 C. 4  D. 8
正确答案： C
解析：一个字节是8位，32位整型变量，占用４个字节，选（C）

4).若有如下程序段，其中s、a、b、c均已定义为整型变量,且a、c均已赋值（c大于0）
s = a;
for （b = 1; b <= c; b++） s = s - 1;
则与上述程序段功能等价的赋值语句是（）
A. s = a - c; B. s = a - b;
C. s = s - c; D. s = b - c;
答案:A

5).设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）
A. 7 B. 10 C. 6 D. 8
正确答案： A   
答案x, 2^6 < x < 2^7

一）水仙花数   page73
求100-999中的水仙花数。若三位数ABC,ABC=A^3+B^3+C^3，则称ABC为水仙花数。
请列出所有的水仙花数

二）输出所有形如aabb的四位完全平方数     page74

三）coj1020完美数
什么是完美数？一个数的所有真约数的和等于自己就是完美数。
 比如：
 6的真约数有1、2、3，且这些真约数加起来1+2+3等于6；
 又比如：28
 28的真约数有1、2、4、7、14，它们加起来还是等于28。
【输入格式】
 输入两个整数x和y（1<=x<=y<=10000）。
【输出格式】
  输出x~y（包含x和y）的所有完美数。一行一个，从小到大。
【样例输入】
 1 100
【样例输出】
 6
 28

四）c1025自守数
 输入两个正整数A 和 B（1<=A<=B<=40000)，求A~B的所有自守数。
什么是自守数？请看：
例如：5^2=5*5=25；25^2=25*25=625；76^2=5776；9376^2=87909376 ，看懂了吗？
就是S=X^2  ，在S的末尾有一个X。这就是自守数。

2019CSP day1t1 格雷码  P5657
题目描述
通常，人们习惯将所有 n位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00,01,11,10。
格雷码（GrayCode）是一种特殊的 n位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。
所有 2位二进制串按格雷码排列的一个例子为：00，01，11，10。
n位格雷码不止一种，下面给出其中一种格雷码的生成算法：
1位格雷码由两个 1 位二进制串组成，顺序为：0，1。
n+1位格雷码的前 2^n 个二进制串，可以由依此算法生成的 n 位格雷码（总共 2^n 个 n 位二进制串）按顺序排列，再在每个串前加一个前缀 0构成。
n+1位格雷码的后 2^n 个二进制串，可以由依此算法生成的 n 位格雷码（总共 2^n 个 n 位二进制串）按逆序排列，再在每个串前加一个前缀 1构成。
综上，n+1位格雷码，由 n 位格雷码的 2^n个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 2^(n+1) 个二进制串。另外，对于 n 位格雷码中的 2^n个 二进制串，我们按上述算法得到的排列顺序将它们从 0～2^n-1编号。
按该算法，2

同余方程：
1)如果两个整数a,b，那么必定存在公式a*x+b*y=gcd(a,b);
2)方程 ax + by = m 有解的必要条件是 m mod gcd(a,b) = 0

同余：设m是给定的一个正整数，a、b是整数，若满足 m|(a-b)，则称a与b对模m同余，记为a≡b(mod m)，或记为a≡b(m)
意义相当于 a=b+km(k∈Z)；
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)

一）碾转相除法求gcd
　　int gcd(int m,int n){   return m%n==0?n:gcd(n,m%n);}
　　int gcd(int m,int n){   return n==0 ? m:gcd(n,m%n);}//或

二）扩展欧几里德，可以同时求出最小的x,y;
模板：
 int gcdEx(int a,int b,int*x,int*y)
{
    if(b==0)
    {
        *x=1,*y=0 ;
        return a ;
    }
    else
    {
        int r=gcdEx(b,a%b,x,y);