By WenJian
【整除】
设a,b为整数，且a不为0，如果存在一个整数q，使得a*q=b,则b能被a整除，记为a|b，且称b是a的倍数，a是b的因子。
整除的几个性质：
（1）如果a|b且b|c，则a|c ；
（2）a|b且a|c等价于对于任意的整数x，y，有a|(bx+cy) ；
（3）设m不为0，则a|b等价于ma|mb ；
（4）设整数x,y满足下式：ax+by=1，且a|n，b|n，那么(ab)|n ；
（5）若b=q*d+c，那么d|b的充要条件是d|c ；
<补充拓展>
（1）若2能整除a的最末位，则2|a
（2）若4能整除a的末两位，则4|a
（3）若8能整除a的末三位，则8|a
（4）若3能整除a的各位数字之和，则3|a
（5）若9能整除a的各位数字之和，则9|a
（6）若11能整除a的偶数位数字之和与奇数位数字之和的差，则11|a
（7）能被7、11、13整除的数的特征是：这个数的末三位与末三位以前的数字所组成数之差能被7、11、13整除。
【GCD与LCM】
一般的，设a1,a2,a3,……ak是k个正整数，如果存在一个正整数d，使得d|a1,d|a2,……d|ak,那么d则为a1,a2,……ak的公约数，其中最大的称为最大公约数，即为gcd(a1,a2,……,ak)，显然它是存在的，至少为1。当gcd=1时，称这n个数是互质的或既约的。公约数一定是最大公约数的约数。
一般的，设a1,a2,a3,……ak是k个正整数，如果存在一个正整数d，使得a1|d,a2|d,a3|d,……ak|d,那么d则为a1,a2,……ak的公倍数，其中最小的称为最小公倍数数，记为lcm(a1,a2,……,ak)，显然它是存在的。公倍数一定是最小公倍数的倍数。
定理：lcm(a,b)*gcd(a,b)=a*b
<欧几里德算法（辗转相除法）>
gcd(a,b)=gcd(b,a%b)
性质：若a,b为偶数，则gcd(a,b)=2*gcd(a/2,b/2)；
若a偶b奇，则gcd(a,b)=gcd(a/2,b)；
代码：
long long gcd(long long x,long long y){
if(x>y)return gcd(y,x);
if(x==0)return y;
return gcd(y%x,x);
}
【勾股数】
对于正整数x，y，z，如果满足等式：x^2+y^2=z^2,则称这组整数（x,y,z）为勾股数。换句话说，凡是可以构成直角三角形的整数即称为勾股数。
x，y，z两两互质的勾股数称为基本勾股数，如（3，4，5），（5，12，13）,其他勾股数称为派生勾股数。基本勾股数乘以一个系数则可以得到派生勾股数。
基本勾股数的奇偶性？
一定是二奇一偶，且最大的为奇数。
所有的基本勾股数都可以写成如下形式：
x=2mn,y=m^2-n^2,z=m^2+n^2 (m>n)
通过它可以枚举基本勾股数。
<勾股数完全公式>
a=m，b=(m^2/k-k) / 2，c=(m^2/k+k)/2 其中m≥3
⒈ 当m确定为任意一个≥3的奇数时，k={1，m^2的所有小于m的因子}
⒉ 当m确定为任意一个 ≥4的偶数时，k={m^2 / 2的所有小于m的偶数因子}
通过此公式可以求出所有的基本勾股数和派生勾股数，并可以求出给定a
时勾股数的组数。
<求勾股数的组数>
当a给定时，不同勾股数组a，b，c的组数N等于①式中k的可取值个数
⒈ 取奇数a=P1^M1×P2^M2×……×Pr^Mr，其中k={1，a^2的所有小于a的因子}，则k的可取值个数：
N=[(2*M1+1)×(2M2+1)×……×(2Mr+1)－1]/2
⒉ 取偶数a=2^M0×P1^M1×P2^M2×……×Pr^Mr，其中k={a^2/2的所有小于a的偶数因子}，则k的可取值个数：
N=[(2M0－1)×(2M1+1)×(2M2+1)×……×(2Mr+1)－1]/2
其中，P1，P2，……，Pr为互不相同的奇素数，M0，M1，……，Mr为幂指数。
【模运算的相关】
<小整数的幂取模>
#define LL long long int
LL power(int a,int b,int p) //a^b%p
{
int t=a,res=1;
while(b)
{
if(b&1)
res=res*t%p;
t=t*t%p;
b>>=1;
}
}
<大整数的模乘法>
#define LL long long int
LL mul(LL a, LL b, LL p) //a*b%p
{
LL rn=0, i;
for(i=1; i<=b; i<<=1,a=(a<<1)%p)
if(b&i)
rn=(rn+a)%p;
return rn;
}
<大整数的幂取模>
#define LL long long int
LL ksm(LL a, LL b, LL p)
{
LL rn=1;
for(; b; a=mul(a,a,p),b>>=1)
if(b&1)
rn=mul(rn,a,p);
return rn;
}
【素数】
对于一个正整数n，如果它的约数只有1和n，则称n为质数。质数不包含1。
（1）素数有无穷多个。
（2）不超过n的素数个数可粗略估计为n/ln(n)
（3）任何大于1的非素数n，那么在[1,sqrt(n)]区间内至少存在一个素数。
<整数唯一分解定理>
任意一个大于1的整数n，均可以表示为若干个素数的乘积，且这个形式是唯一的。
n=p1^m1*p2^m2*……pk^mk
其中,p1,p2,……pk 为n的质因子。
<简单的素数判断>
bool prime(int num)
{
for(int i=2;i*i<=num;i++)
{
if(num%i==0)
return 0;
return 1;
}
}
[ 更快的Miller-Rabin素数判定法]
<线性时间筛素数>
（1）
const in MAXN=1000000+10;
const int MAXP=70000;
int vis[MAXN];
int prime[MAXP]
void sieve(int n)
{
int m=(int)sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
if(!vis[i])
for(int j=i*i;j<=n;j+=i)
vis[j]=1;
}
（2）
int prime[MAXP];
bool flag[MAXN];
int j=0;
for(int i=2;i<=n;i++)
{
if(flag[i]==0)
prime[j++]=i;
for(int k=0;k<j;k++)
{
if(prime[k]*i>n)break;
flag[prime[k]*i]=1;
if(i%prime[k]==0)break;
}
}
【同余】
若a%m=b%m,则称a与B关于模m同余，记为a≡b(mod m)
性质：
（1）自反性： a≡a(mod m)
（2）对称性：若 a≡b(mod m)，则 b≡a(mod m)
（3）传递性：若a≡b(mod m)，b≡c(mod m)，则 a≡c(mod m)
（4）同加性：若a≡b(mod m)，则a+c≡b+c(mod m)
（5）同乘性：若a≡b(mod m)，则a*c≡b*c(mod m)
若a≡b(mod m),c≡d(mod m),则有a*c≡b*d(mod m)
（6）同幂性：若a≡b(mod m)，则an≡bn(mod m)
（7）若a%p=x,a%q=x,且p,q互质，则a%(p*q)=x
<同余分配率>
加法分配率：(a+b)%n=(a%n+b%n)%n
减法分配率：(a-b)%n=(a%n-b%n)%n
乘法分配率：(a*b)%n=a%n*b%n%n
除法不满足分配率,但有这个性质：(a/b)%n=a%(bn)/b
<剩余系>
给定n，则所有整数对n取模，将得到一个集合，称为模n的剩余系，即{0,1,2,……,n-1}.
n的剩余系中与n互质的数称为简化剩余系，也称为缩系。n的剩余系记为Zn，而n的缩系记为Zn*.
模n的剩余系中，每个元素都代表所有与它同余的整数，比如n=7，则1代表{1,8,15,22,……}，这个集合满足模n同余关系，称为同余等价类。
<威尔逊定理>
若p为素数，则(p-1)!≡-1(mod p)。 其逆定理也成立。
<费马定理>
若P为素数，a为正整数，且a和P互质，则有：a^p-1≡ 1(mod p)
<欧拉定理>
欧拉函数phi：不超过n的且与n互质的正整数的个数。
如果n为素数p，则 phi(p)=p-1
如果n为素数p的幂次p^a，则 phi(p^a)=(p-1)*p^(a-1).
欧拉函数为积性函数：如果n为任意两个互质的数a、b的积，则 phi(n)= phi(a)* phi(b)
n=p1a1*p2a2*……*pkak
则 (n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)
欧拉定理：
若a与m互质，则
<欧拉函数计算>
（1）
int euler(int n)
{
int m=(int)sqrt(n+0.5);
int ans=n;
for(int i=2;i<=m;i++)if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
return ans;
}
（2）此方法更快
int phi[maxn];
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);
}
}
<扩展欧几里得算法>
对于任意整数a，b，一定存在整数x、y，使得ax+by=gcd(a,b)若gcd(a,b)=1,则一定存在整数x，y，使得ax+by=1可以使用扩展欧几里德算法求出x，y。
void gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b){x=1;d=a;y=0;}
else {
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
x即为a的逆元。
运用：
（1）求二元一次方程：ax+by=c
（2）求模线性方程：ax≡b (mod n)
（3）求逆元：ab≡1 (mod n)
（4）求gcd(a,b)
<模线性方程&中国剩余定理>
有如下方程：
其中n1，n2，……，nk互质。
中国剩余定理正是用来求解模线性方程组的。
对于n1，因为它与(n2*n3……*nk)互质，我们可以找到一个系数z1，使得z1*(n2*n3*……nk)%n1=1。设z1*(n2*n3*……*nk)为c1。
同理，对于每个nk，都可以找到一个zi，使得zi*(n1*n2*……*nj |j!=i)%ni=1，设zi*(n1*n2*……*nj |j!=i)为ci。
x=b1*c1+b2*c2+……bk*ck+m(n1*n2*…*nk) 其中m为任意整数。
x为一组解。
<模乘法的逆>
如果(a*b)%n=1,则称a与b模n互为倒数，记为a=b^(-1) ，b=a^(-1),这是模乘法的逆。
若a与n互质，则必存在一个整数b，使得a*b%n=1,即a模n的逆元一定存在。
若b存在逆元，则有(a/b)%n=(a*b^(-1))%n。
证明：设b的逆元为c，则bc%n=1
(a/b)%n=((a/b)*bc)%n=a*c%n=a*b^(-1)%n
【例题】
1.删数
对于给定的n，从1!,2!…,n!中至少删除几个数，才可以使得剩下的数的乘积为完全平方数？
输入：一个整数n（1<=n<=50）
输出：第一行表示最少需要删去的数的个数。
接下来输出一种删数方案，如果有多种方案，任意输出一种即可。
2.质因数分解
给定一个整数n(n<10000),求n！的质因数分解。
输入：一个整数n
输出：若干行，每行两个数。第一个数表示质因子，第二个数表示它的个数。
所有质因子按照从小到大的顺序排列。
输入样例：
5
输出样例：
2 3
3 1
5 1
3.n!的位数
输入n，求n！的位数。（n<100000）
4.费马二平方素数
除2这个特别的素数外，所有的素数都可以分为两类，第一类是被4除1的素数，如5，13，17，29；第二类是被4除余3的素数，如3，7，11，19.很奇怪的是：第一类素数都能表示成两个整数的平方和，第二类则不能。
如5=1×1+2×2
13=2×2+3×3
17=1×1+4×4
29=2×2+5×5
这就是著名的费马二平方定理。有趣的是，上述有的等式右侧的数又恰恰是两个素数，如上面的13和29两个数的等号右侧就都是素数，我们把这样的素数取名为"费马二平方素数"。即如果一个素数F能够表示称为两个素数的平方和形式F=A*A+B*B,其中A,B都是素数，那么它就是费马二平方素数。
编程输出N以内的所有费马二平方素数（N<=2*10^9）
5.code feat
有一个正整数N满足C个条件，每个条件都形如“它除以X的余数在集合{Y1,Y2,…Yk}中”，所有条件中的X两两互素，你的任务是找出最小的S解。
输入格式：包含若干组数据，每组数据的第一行为两个整数C和S(1<=C<=9,1<=S<=10),以下C行每行描述一个条件，首先是整数X和k,(X>=2,1<=k<=100),然后是Y1,Y2,…Yk(0<=Y1,Y2,…Yk<X).所有X的乘积保证在32位整型范围内。输入结束标记为C=S=0.
输出格式：对于每组数据，输出S个最小正整数解，并按照从小到大的顺序排列。
6.A/B
要求求出A/B%9973的值。但由于A很大，所以只给出n=A%9973的值。保证B和9973互质，且A必定能被B整除。n<9973,B<10^9。
7.Luckiest Number
给出一个整数L(L<2000000000)，找到一个最小的全由8组成的L的倍数。若存在，则输出该数的位数，若不存在，则输出0.
8.Description has only two sentences
an = X*an-1 + Y and Y mod (X-1) = 0.
Your task is to calculate the smallest positive integer k that ak mod a0 = 0.
INPUT：Each line will contain only three integers X,Y,a0(1<x<2^31,0<=Y<2^63,0<a0<2^31)
OUTPUT：For each case, output the answer in one line, if there is no such k, output "Impossible!".
9.Happy 2004
Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29).
Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.
INPUT：The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000). A test case of X = 0 indicates the end of input, and should not be processed.
OUTPUT：For each test case, in a separate line, please output the result of S modulo 29.
Coding by SinGuLaRiTy
Time : 2017-02-07