数论
一、数论的相关知识
1、整除
（1）、概念：设a是非零整数，b是整数。
如果有一个整数q，可以让b=a*q，则a|b，也就是b是a的倍数，a是b的因数。
比如说：4|8，7|21 ........
（2）、性质：
1、若a|b，b|c，则a|c
2、若a|b，a|c，则a|b±c
3、若a|b，a|c，则a|(b*x+c*y)（x、y为整数）
4、若a|b，m≠0，则(m*a)|(m*b)
5、若a|n，b|n，且存在整数x,y使a*x+b*y=1，则(a*b)|n
6、若b=q*d+c，d|c，则d|b。（若b=q*d+c，d|b，则d|c）
这些性质看似用不到编程上，但是在一些题目中使用会大大降低编程的难度以及时间复杂度。
2、同余
（1）、概念：设a,b均为整数，且a-b能被某个自然数m整除，则a≡b(mod m)，也就是存在一个整数k使：a-b=m*k
（2）、性质：
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)
6、若a≡b (mod m)，则a^c≡b^c (mod m)（a^b表示a的b次方）
7、分配律
(a±b)%m=(a%m±b%m)%m
(a*b)%m=(a%m*b%m)%m
除法不满足分配律，但是满足(a/b)%m=a%(b*n)/b
3、最大公因数与最小公倍数
（1）、概念：不用说了吧...........，a,b的最大公因数记为：GCD(a,b)，a,b的最小公倍数记为：LCM(a,b)
当GCD(a,b)=1时，则a，b互质。
（2）、性质：
1、GCD(x,y)=GCD(x,y-x)=GCD(y,x%y)（辗转相除法原理）
2、x*y=GCD(x,y)*LCM(x,y) >>>>> LCM(x,y)=x*y/GCD(x,y)
4、素数
（1）、概念：一个除1和它本身以外，没有其他因数的数，1不是素数。
（2）、性质：
1、唯一分解定理
2、威尔逊定理：若p是素数，则(p-1)!≡-1(mod p) （其中!表示阶乘）（其逆定理也成立）
3、费马定理：若p是素数，a是正整数，且a、p互质，则a^(p-1)≡1(mod p) （其逆定理不成立）
（3）、欧拉函数：φ(n)表示1~n之间与n互质的数。
（4）、欧拉定理：
1、若p为素数，则φ(p)=p-1
2、若p为素数，则φ(p^a)=(p-1)*p^(a-1)
3、若a,b互质，则φ(a*b)=φ(a)*φ(b)
4、若a,m互质，则a^φ(m)≡1 (mod m)
讲了这么多，来看一道例题吧
二、例题
洗牌机
题目描述
有2n张牌，放在2n个从1到2n的有序位置上。洗牌机每次可以把第i张牌洗到p（i）的位置上。P（i）的定义如下：
问经过最少多少轮洗牌，才会使所有牌回到原来的位置。
输入
输入格式：
有多组数据，每组数据一个整数n(n<=109）
输出
输出格式：
对于每组数据，输出一个整数，表示答案。
样例输入
1
样例输出
2
4、当p(i)再次等于1时，k就是答案，原问题就转化为：2^k≡1 (mod 2*n+1)，已知n，求最小的k。
5、因为2与2*n+1互质，由欧拉定理可知：2^φ(2n+1)≡1 (mod 2n+1)，所以k=φ(2n+1)。
6、当n=3时，k=φ(2n+1)=6，但是k的最小值为3，洗牌过程如下。
1 2 3 4 5 6
4 1 5 2 6 3 (1)
2 4 6 1 3 5 (2)
1 2 3 4 5 6 (3)
7、我们可以找φ(2n+1)的因子q，如果q满足2^q≡1 (mod 2n+1)时（通过快速幂算法来计算），q就是k的最小值。
代码：
#include<cstdio>
#include<cmath>
long long m,n,x,ans;
long long P(long long x,long long y,int mod)
{long long ans=1;while(y){if(y&1) ans=(ans*x)%mod;y>>=1;x=x*x%mod;}return ans;
}
long long phi(long long n)
{long long m=(long long)sqrt(n+0.5),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;
}
int main()
{int i;while(~scanf("%lld",&n)){m=2*n+1;x=phi(m);ans=x;for(i=2;i*i<=x;i++){if(x%i==0){if(P(2,i,m)==1)if(i<=ans){ans=i;break;}if(P(2,x/i,m)==1)if(x/i<=ans){ans=x/i;}}}printf("%lld\n",ans);}
}