数学总结
素数，因子
1.大区间素数
POJ-2689 Prime Distance
题意：题意：求给定区间内的质数距离最小的一对和质数距离最大的一对。(1 <= L,R <= 2.1E9, R-L <= 1e6)
大区间的素数题都是这样做的。筛出不超过R的所有质数p，然后再去枚举[L,R]区间内p的倍数，将其打上标记，最后区间内剩下的就都是素数了。这对于每个质数是logn的。
在打标记时发现由于数值很大，bitset120M开1e9，所以此题将数组平移L。就只用开1e6.
注意:1需要特判不是素数。
2.反素数思想：枚举因子
ZOJ 2562 More Divisors
题意：给定一个n (1<=n<=10^16)，求小于等于n的最大反素数。
反素数：比它小的数的约数个数都小于它。
就是求小于等于n的约数最多的数。有约数个数定理：
X=p1k1∗p2k2∗p3k3∗p4k4...pnkn
X的约数个数为：
Y=(1+k1)(1+k2)(1+k3)...(1+kn)
要约数最多，我们就结合反素数这种思想。dfs搜索每个质因子，对于每个质因子枚举它的指数。
const ll inf = 999999999999999999;
ll pri[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67},best,ans,n;
void dfs(ll dep,ll tmp,ll num){
if(dep >= 16) return;
if(best < num) {
best = num;
ans = tmp;
}
if(best == num) ans = min(ans,tmp);
for(int i = 1; i <= 63; ++i){
if(pri[dep] > n / tmp) break;
dfs(dep + 1,tmp *= pri[dep],num * (i + 1));
}
}
int main(){
while(~scanf("%lld",&n)){
best = 0;
ans = inf;
dfs(0,1,1);
printf("%lld\n",ans);
}
return 0;
}
HDU 6216 A Cubic number and A Cubic Number
题意：判断一个素数是否是两个立方数之差，就是验差分。。
只有相邻两立方数之差才可能，因为x3−y3=(x−y)(x2+xy+y2)，看(x-y)，就能很快想到不相邻的立方数之差是不可能是素数的.
然后把y=x+1代入，得：p=3x2+3x+1，所以可得判断条件为：①p-1必须能被3整除；②(p-1)/3必须能表示为两个相邻整数之积。
POJ 3421 X-factor Chains
题目大意：一个数列，起始为1，终止为一给定数X，满足Xi < Xi+1 并且Xi | Xi+1。
求出数列最大长度和该长度下的情况数。
很简单想到将X分解质因数，这样我们每加一个数就是前一个数*其中一个质因数即可。所以长度为质因数个数。
情况数就是这些素因子的排列组合数。需要去重。
同余
1.换模问题
POJ 1845 Sumdiv
在经典不过的数论求约数和的问题。
求AB的所有约数和。
$ A = {p_1^{c_1} * p_2^{c_2} * …*p_n^{c_n}}$
$ A^B= {p_1^{c_1B} * p_2^{c_2B} * …p_n^{c_nB}}$
$sum = (p_1^0 + p_1^1 + …+p_1^{c_1B}) * (p_2^0 + p_2^1 + …+p_2^{c_2B}) $
有两种方法：
1.用等比数列求和公式，注意求和时候模的mod是转换后的模值。
2.用分治，分奇偶两种情况。
void make_prime(ll m){
for(ll i = 2; i <= m; ++i){
if(!flg[i]) pri[++cnt] = i;
for(ll j = 1; j <= cnt && pri[j] <= m / i ; ++j){
flg[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
ll Mul(ll a,ll b,ll c){
a %= c;ll ret = 0;
while(b){
if(b & 1) ret = (ret + a) % c;
a = (a + a) % c;
b >>= 1;
}
return ret;
}
ll Power(ll a,ll b,ll c){
a %= c;ll ret = 1;
while(b){
if(b & 1) ret = Mul(ret,a,c) % c;
a = Mul(a,a,c) % c;
b >>= 1;
}
return ret;
}
int main(){
make_prime(50000);
A = read();B = read();
ll t = sqrt(A) + 1,i = 1;
while(A > 1 && pri[i] <= t){
if(A % pri[i] == 0){
p[++num] = pri[i];
while(A % pri[i] == 0){
A /= pri[i];
a[num]++;
}
}
++i;//!!
}
if(A > 1){ // !!
p[++num] = A;
a[num] = 1;
}
for(ll i = 1; i <= num; ++i){
ll P = (p[i] - 1) * mod;//!!!!换模！！！！
ll up = (Power(p[i],a[i] * B + 1,P) - 1 + P) % P;
sum *= (up / (p[i] - 1)) % mod;
sum %= mod;
}
printf("%lld\n",sum);
return 0;
}
这道题是单组数据，不需要筛素数表，不管是枚举质数，还是每个可能成为因子的数，分解质因数的时间复杂度都是O（N）
但如果是所有数都需要枚举因子，就枚举每个因子，时间复杂度O(nlogn)
HDU 5690 All X
F(x,m) 代表一个全是由数字x组成的m位数字。请计算，以下式子是否成立：
F(x,m) mod k≡c
1≤x≤9，1≤m≤1010，0≤c
F(x,m)=xx...x=910m−1∗x;数据范围太过毒瘤，要快速幂套快速幂。
注意向SUMDIV一样要换模。$\frac{(10^m−1)%9k}{9}∗x%k=c%k $
POJ 2657 Comfort
题意:n个点顺时针围成一圈（编号1~n），初始时在1点，每次可以顺时针移动k点，n个点中有一些点有障碍物，求最小的k使得在不经过任何一个有障碍物的点就可以到达z点
为方便取模，先将所有点编号减一变成0~n-1，从1到z枚举k，对于每个k，如果一元线性同余方程k*x=z(mod n)有解g（此处g为最小正整数解），说明每次跳k步可以到达z点，之后枚举每个障碍物判断是否会经过障碍物，对于某障碍物ob[i]，如果有解且最小正整数解y<g，说明会经过这个障碍物，否则不会经过，以此来判断当前k是否满足条件，第一次遇到满足条件的k一定为最小的k.
拓展欧几里得：
hdu 1576 A/B
要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973).(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
$A = 9973 * k + n $
A=t∗B
于是9973∗k+n=t∗B
左右互换一下：n=t∗B+9973∗k
然后就可以用exgcd求t∗B+9973∗k=1
最后输出t∗n即可
UVA 12169 不爽的裁判
题意:随机选取x1,a,b，根据公式xi=(a∗xi−1+b)%10001得到一个长度为2*n的序列，奇数项作为输入，求偶数项，若有多种，随机输出一组答案
即给出已知的x1,x3,x5,x7……x2k+1，找出a和b，满足递推式，并输出x2,x4,x6……x2k (0<=a,b<=10000)
我们尝试找找x1和x3的关系。
x2=(a∗x1+b)%10001
x3=(a∗x2+b)%10001
带入得，
x3=(a∗((a∗x1+b)%10001)+b)%10001
x3=(a∗(a∗x1+b)+b)%10001
将x3看成a∗(a∗x1+b)+b除以10001的余数
则有 x3+y∗10001=a∗a∗x1+a∗b+b=a∗a∗x1+(a+1)∗b
再移项 x3−a∗a∗x1=(a+1)∗b−y∗10001
所以我们枚举a，解出b，再用其他项验证。
注意不定方程ax+by=c有解的条件是gcd(a,b)∣c
UVA 12716 GCD 和 XOR
题意：输入整数n（1<=n<=3*10^7），有多少对整数（a，b）满足：1<=b<=a<=n，且gcd（a，b）=a XOR b。例如：n=7时，有4对：（3，2），(5,4），(6,4），(7,6）
本题的主要想法就是找到一个沟通gcd（a,b）和a xor b的桥梁.
a xor b≥a−b。假如二进制位上相同，那么都是0，加入二进制位上不同，前者一定是1，后者可能是1（1-0）或-1（0-1）
a−b≥gcd(a,b)。因为gcd(a,b)=gcd(a,a−b)=gcd(b,a−b)显然a−b≥gcd(a,a−b)，得证.
我们现在已知gcd（a,b）=a xor b，根据夹逼法，a xor b=a−b=gcd(a,b)=gcd(a,a−b)
所以如果a和b是满足题意的二元组，前提是a−b是a的因子
因此我们枚举a−b，求得它的所有倍数，再判断a−b=a xor b是否成立。
时间复杂度O(N+N/2+N/3+……+N/N)=O(NlogN)
注意：这类题是不可能一个一个枚举因子的.时间复杂度O(N）
它只可能利用上式O(N+N/2+N/3+……+N/N)=O(NlogN)枚举所有的倍数或因子。
逆元
HDU 5976 Detachment
题意：给一个数N(N<=10^9)，让你把它拆成若干各不相同的数Ai，ΣAi=N，要求ΠAi（累乘）最大。
在简单枚举后发现ai应该从2开始，并且取连续的自然数。但是我们拆到最后可能会剩下一个数x。我们把x从后均摊到每一个ai上。然后就是一个阶乘加上逆元就能搞定的事。
欧拉函数
HDU 4983 Goffi and GCD
题目大意：给你N和K,问有多少个数对满足gcd(N-A,N)*gcd(N-B,N)=N^K。
题解：由于 gcd(a, N) <= N,于是 K>2 就无解。
K=2 只有一个解 A=B=N。
K=1的话我们枚举gcd(A,N)=g,那么gcd(B,N)=N/g。问题转化为统计满足gcd(A,N)=g的A的个数。这个答案就是 φ(N/g)。答案是Σφ(N/g)∗φ(g)(g∣N)。
HDU 2588 GCD
题意：输入 N 和 M (2<=N<=1000000000, 1<=M<=N),找出所有的X满足1<=X<=N 且 gcd(X,N)>=M.
思路：枚举N的大于等于M的公约数g[i]，结果为所有∑φg[i]n的欧拉函数的值的和
排列组合
HDU 5894
题意：m个人需要坐在有n个座位的圆桌上，使得任意两个人之间距离至少为k，座位都不相同，人可以看做相同，求方案数。
可以想象成每一个人后面至少跟着k个座位
当一个人的位置确定以后，就变成了sum = C(n - 1 - m * k ，m - 1)
因为第一个人选取的位置可能是任意一个座位，所以sum * n
因为可能所有人都成为第一个人，所以ans = sum * n / m
题目大意：
在一个 n x m 的矩阵中插入任意数字，使得每一行每一列数的乘积为 k，其中 k要么是 1 要么是 -1. 我们注意到插入的数只可能是 1 或 -1.
我们只考虑 -1 的数目。当 k=-1 时，每行每列有奇数个 -1，其他的为 1；当 k=1 时，每行每列有偶数个 -1，其他的为 1. 但是你添入一个数会同时影响到一行和一列，又因为数据范围比较大，直接模拟肯定是行不通的，应该存在某个公式。
换种思维考虑，现在把最后一行和最后一列空出来，其他的空无论添任何值，我们都可以通过在最后一行和最后一列添加 1 或 -1 使得满足题意，因为这样我们可以控制 -1 的奇偶。所以有$ (n-1)(m-1)$ 个值是可以任添的，每个空有 2 种选择，所以结果是$ 2^{(n-1)(m-1)} $，直接做会超时，可以用快速幂取模。
注意，当 k=-1 时，如果行列的奇偶性质不同，则怎么填都会有冲突，所以这个时候答案是 0，需要特判。
CodeForces 888D Almost Identity Permutations
给出n和k计算满足至少有(n-k)个位置的值a[i]==i的1~n的全排列的个数。k<=4
观察题目数据范围，发现k的取值范围只有1~4，故考虑能否直接分类讨论找出数学公式。
当k=1时,显然无法做到只有一个位置a[i]!=i，即只有一种全排列。
当k=2时，我们先去考虑有且只有两个位置a[i]!=i的数目，显然我们需要从1~n中取出一个二元组 < i , j > (其中i < j),然后将他们每个二元组交换顺序即可，容易发现二元组数目为C(n,2),答案加上k = 1的情况即可。
当k=3时，我们先去考虑有且只有三个位置a[i]!=i的数目，显然我们需要从1~ n中取出一个三元组<i,j,k>(其中i<j<k),然后将他们每个三元组交换顺序且每个数都不在原来的位置上，容易发现三元组的数目为C(n,3),且对于每个二元组满足条件的排列数为2.
比如对于<1,2,3>来说，满足的交换顺序有<2,3,1>,❤️,1,2>。
所以答案为三元组数目∗2+(k=2的数目)+(k=1的数目)
当k=4时，同上面的分析可知，四元组的数目为C(n,4).然后对于每个四元组，满足的排列数为9.
所以答案为四元组数目∗9+(k=3的数目)+(k=2的数目)+(k=1的数目)
UVA 10375 选择与除法
计算C(p,q)/C(r,s)。输出保证不超过10^8，保留5位小数.
就直接算组合数了。
int main(){
double a,b,c,d;
while(~scanf("%lf%lf%lf%lf",&a,&b,&c,&d)){
double ans=1.0;
b=min(a-b,b);d=min(c-d,d);
for(int i=1;i<=max(b,d);++i){
if(i<=b&&i<=d) ans*=(a-i+1)/(c-i+1);
else {
if(i<=b) ans=ans*(a-i+1)/i;
if(i<=d) ans=ans*i/(c-i+1);
}
}
printf("%.5lf\n",ans);
}
return 0;
}
母函数
HDU 1028
题意： 给定整数n，求n有多少种划分方式。（对于4来说，1+3和3+1是同一种划分方式）
分析：以前是用dp做的，现在发现可以用母函数来做，对于整数n，可令G（x）=(1+x+x2+x3+...+xn)(1+x2+x4+...)(1+x3+x6...)...，1+x+x2+x3+...+xn的第i位xi表示1取i次的情况，(1+x2+x4+...)的第i位表示2取i次的情况，依次类推，最后多项式xn的系数就是答案。（类似于邮票问题：有邮票1,2,3，4四张每张邮票，邮票的数量无限多,求出一个数方案的个数。）
int main(){
for(int i = 0; i <= maxn; ++i) a[i] = 1;
for(int i = 2; i <= maxn; ++i){
for(int j = 0; j <= maxn; j += i)
for(int k = 0; j + k <= maxn; ++k)
b[j + k] += a[k];
for(int k = 0; k <= maxn; ++k) a[k] = b[k],b[k] = 0;
}
while(~scanf("%d",&n)) printf("%d\n",a[n]);
return 0;
}
思维
CodeForces 711D Directed Roads
题意：给一个图，n个点n条边，每条边可以反方向，问有多少种方案使得图中没有环。
只要找出图中的环，任意改变（大于等于1小于n）条边，都可以使得一个环不是环。一个环的方案数就是C(1,n)+C(2,n)+C(3,n)+…C(n-1,n)，这个组合数的和为2的n次方减2.
每个连通量必然有一个环，dfs的时候算出每个连通块中点的个数y，算出连通块中环中的点的个数x，所以这个连通块不成环的答案是2y−x∗(2x−2)。
最后每个连通块的答案相乘即可。
CodeForces 689E Mike and Geometry Problem
题意：给出n个线段[li,ri]，求任意k个线段所共同覆盖的点的总和。
对于每一条线段，区间[li,ri]加一，如果一个位置的值为m，那么最后的结果ans += C(m,k);
如果只是离散化端点的话，没法求得中间部分被覆盖的点，所以在离散化时保证相邻两点中间留出一个1，对于中间的点，求出当前的值*(相邻两点实际距离-1)即是结果。
错排
f(1)=0,f(2)=1,f(n)=(n-1)*[f(n-1)+f(n-2)]
矩阵乘法
POJ 3070 Fibonacci
题意：就是让你求斐波拉切数列的第n项的后面四位。
分析：矩阵快速幂优化dp。
注意E是(i,i)=1,其他为0.
UVA10870 Recurrences
题意：计算f(n) = a1 f(n - 1) + a2 f(n - 2) + a3 f(n - 3) + … + ad f(n - d). d<=15
在上题的基础上变成了多个。构造转移矩阵。
POJ 3233 Matrix Power Series
给定矩阵A，求A + A^2 + A^3 + … + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
矩阵的逆（类似数的逆元）我不会。就只能分治了。
struct matrix{
int a[maxn][maxn];
matrix(){memset(a,0,sizeof(a)); }
void print(){
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) printf("%d ",a[i][j]);
printf("\n");
}
}
}e;
inline matrix add(matrix A,matrix B){
matrix C;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
C.a[i][j] = (A.a[i][j] + B.a[i][j])% mod;
return C;
}
inline matrix mul2(matrix A,matrix B){
matrix C;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
return C;
}
inline matrix mul1(matrix A,int k){
matrix ret = e;
while(k){
if(k & 1) ret = mul2(A,ret);
A = mul2(A,A);
k >>= 1;
}
return ret;
}
inline matrix solve(matrix A,int b){
matrix C;
if(b == 1) return A;
if(b % 2 == 1) return add(mul1(A,b),mul2(add(mul1(A,b / 2),e),solve(A,b / 2)));
return mul2(add(mul1(A,b/2),e),solve(A,b / 2));
}
int main(){
scanf("%d%d%d",&n,&k,&mod);
matrix A; for(int i = 1; i <= n; ++i) e.a[i][i] = 1;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d",&A.a[i][j]);
solve(A,k).print();
return 0;
}
HDU 4965 Fast Matrix Calculation
题意：给出N∗K的矩阵A和K∗N的B，求(AB)N∗N结果矩阵中各元素模6 之和。（n<=1000,k<=6)
A∗B的矩阵是N∗N的矩阵，快速幂会超时，用乘法结合律AN∗N∗BN∗N分别计算。
POJ 3150 Cellular Automaton
题目大意：给定n（1<=n<=500）个数字和一个数字m，这n个数字组成一个环(a0,a1…an-1)。如果对ai进行一次d-step操作，那么ai的值变为与ai的距离小于d的所有数字之和模m。求对此环进行K次d-step（K<=10000000）后这个环的数字会变为多少。
拿样例来说：
a矩阵：
a = 1 2 2 1 2
构造转移矩阵：
b =
1 1 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 1 1 1
1 0 0 1 1
POJ 3734_Blocks
题意：用红，绿，蓝，黄，四种颜色对一序列n个方块涂色，求出绿和红色方块数同时为偶数的染色方案数。mod=10007
dp+矩阵快速幂
首先明确有三种状态：
红和绿均为偶数
红和绿只有一个为奇数
红和绿均为奇数
设前三种方案数分别为ai，bi，ci，则可以得到以下递推式：
ai+1=2∗ai+bi
bi+1=2∗ai+2∗bi+2∗ci
ci+1=2∗ci
HDU 2604 Queuing
题意：给你n个人，排成一个长度是n的队伍，人只有两类f,m，问可以有多少种排法使度列中不出现fff，fmf这样的子串。
用f(n)表示n个人满足条件的结果，那么如果最后一个人是m的话，那么前n-1个满足条件即可，就是f(n-1)；
如果最后一个是f那么这个还无法推出结果，那么往前再考虑一位：那么后三位可能是：mmf, fmf, mff, fff，
其中fff和fmf不满足题意所以我们不考虑，
如果是 mmf的话那么前n-3可以找满足条件的即：f(n-3)；
如果是mff的话，再往前考虑一位的话只有mmff满足条件即：f(n-4)
所以f(n)=f(n-1)+f(n-3)+f(n-4)
BZOJ 1297 SCOI2009 迷路
题目大意：有向图里10个点，点与点之间距离不超过9，问从1刚好走过T距离到达n的方案数。
当时看到这题就想到了某道奶牛题（在图论在总结里）。
这两道题的区别就是奶牛题问的是走T条边，这道题是每条边都有一个边权求走过T边权的方案数。
所以可以看成奶牛题相当于这一题里的边权为1的情况。首先边权为1就把奶牛题的floyd那段改成矩乘就可以了.
那么接下来考虑边权不为1的情况，因为边权最多为9，我们就可以把每个点拆成9个点，x[1]~x[9]为x拆完的点，x[i]和x[i+1]连一条边权为1的边，然后x到y有一条边权为z的边，那么就把x的第z个点往y的第1个点连一条边.
然后跑矩乘就可以辣。
HDU 2254 奥运
题意：指定v1，v2，要求计算出在t1,t2天内从v1->v2的走法
思路：可以知道由矩阵求，即将其建图A，求矩阵At1+......+At2. An后，A.t[v1][v2]即是从v1到v2要n步
所以先预处理出A1−A10000的情况,后面再注意下细节，计算即可.
循环
UVA 11582 巨大的斐波那契数
输入两个非负整数a、b和正整数n(0<=a,b<2^64,1<=n<=1000)，你的任务是计算f(ab)除以n的余数，f(0)=0, f(1)=1,且对于所有非负整数i，f(i+2)=f(i+1)+f(i)。
观察发现此题上面什么都很大，只有n很小。就可以求出f[]关于n的循环节。再用ab关于循环节取模即可。
康托展开
UVA 1262 密码
给出两个6行5列的字母矩阵，一个密码满足：密码的第i个字母在两个字母矩阵的第i列均出现。
然后找出字典序为k的密码，如果不存在输出NO。(k≤7777)
字典序为K。康托展开。
先把每个位置能填的数全部预处理出来，以样例为例：{ACDW}、{BOP}、{GMOX}、{AP}、{GSU}
一共43423=288种
逆展开：比如k=197。
197÷（342*3）=2……53 所以第一位选D
53÷（423）=2……5 所以第二位选P
5÷（2*3）=0……5 所以第三位选G
5÷（3）=1……2 所以第四位选P
2÷（1）=2……0 所以第五位选U
与康托展开略有不同的是可选的字母是固定的，不会因为之前选的而导致名次的改变。