[转]pku数学类算法题目小结

旧城等待， 2022-08-05 08:46 242阅读 0赞

感觉总结的比较全面,转给大家:

pku 1150 The Last Non-zero Digit  
和计算排列数末尾有多少个零有些类似，把2，5因子都拿出来，剩下的数的最后一个数字只有1，3，7，9。只有各位上的数字才会影响最后一个非零数字。统计可以用递归来统计，求出1～n中因子2，5的个数，以及3，7，9结尾的数和去掉2，5后新的到的数中3，7，9结尾的数。结果就是 2^(dig\[2\]-dig\[5\])\*3^(dig\[3\])\*7^(dig\[7\])\*9^(dig\[9\]) mod 10 ，用快速幂乘来算。

pku 1186 方程的解数 (hash,枚举)  
题目给出最多有6个未知数，未知数的取值在\[1,150\]之间，直接枚举时间复杂度是150^6，这个时间不能接受。枚举前一半的未知数可以到达的值(用hash表保存)，再枚举后一半，这样可以加快枚举。

pku 1285 Combinations, Once Again（有重复的组合，dp）  
对输入的数先统计一下，每个数出现的次数。如果每次重复的数，输出c\[n\]\[m\]就可以。有重复数时，要考虑到取相同元素的情况，那么ans=sigma c\[x\]\[i\]\*z\[s\]\[m-i\] 0<i<=m z\[i\]\[j\]表示从1到第i堆中拿j个，把重复的数字表示成a\[1\],a\[2\]..,a\[s\],s个数出现重复。注意几个边界条件，c\[0\]\[0\]=1,z\[1\]\[0...a\[1\]\]=1,z\[i\]\[1\]=i 2<=i<=s。

pku 1430 Binary Stirling Numbers (stirling 数)  
在wiki上找到公式，原来mod 2时和组合数有关系。原文如下：

Using a Sierpiński triangle, it's easy to show that the parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:

Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:

then mimic a bitwise AND operation by intersecting these two sets:

to obtain the parity of a Stirling number of the second kind in O(1) time.

pku 1465 Multiple(BFS,整除)

给几个一些数学，找出由这些数字组成的数中最小的一个能整除n的数。0<n<4999,把所有的数从小到大开始，在入队列前看下该数所到达的余数是否被前面小的数求到过，若否才入队。这样搜索的空间就只有n的剩余系了。

pku 1715 Hexadecimal Numbers(组合)

不重复的组合问题，知道第几个找出这个组合。从最高位开始，一位一位确定dfs下去，每次都要保证已确定的位的所有组合不少于题目给出的序号。最多八层。

pku 1737 Connected Graph(组合数学，高精度)

题目是求n个点用边链接，形成联通图的方案总算。满足联通的边数在\[n-1,n(n-1)/2\],自己一开始想分边数情况考虑，发现情况比较复杂，推出一个像整数拆分的方法。还来在网上看到一种更好的解法。公式是f\[n\]=f\[k\]\*f\[n-k\]\*c\[n-2\]\[k-1\]\*((2^k)-1) (c\[n-2\]\[k\]表示组合数,1<=k<n);考虑一个完整的联通图，可以标记两个点1，2。将点1，点2分别划分在两个子联通图中分别为g1，g2。在g1中最少要有一个点与g2中的点2链接。这样的方式共2^k-1中，而g1总有c\[n-2\]\[k-1\]个。将他们乘在一起就有了上面的式子。另外这题要用到高精度，终于用java写了个高精度的题感觉真方便。

pku 1845 Sumdiv(积性函数，因子和)  
求a^b的因子和(包括1和a^b),由于因子和是积性函数。所以f(a^b)=f(p1^t1)\*f(p2^t2)...\*f(pn^tn),对于f(p^t)的情况:  
f(p^t)=1+p+p^2+...+p^t=(p^(t+1)-1)/p-1。题目还要求mod 9901,这虽然是个素数，但是数据中出现了p-1 = 0 (mod 9901)的情况，这时f(p^t)=t+1 (mod 9901),要特殊处理下，其余用快速幂乘。

pku 1809 Regetni（奇偶，组合）  
根据 这个公式计算 A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2 三角形的面积是否为整数。这题不要去算具体的面积，答案和所选点的奇偶性有关，点的只有4种类型，(0,0),(1,1),(1,0),(0,1)。把这4类点的所有组合情况(共20种)代入公式  
发现，当最少有两个点属于同一类型是面积才是整数。那么只有统计出所有点的组合情况就可以得出答案了。点的组合情况  
\{0,1,2\},\{0,1,3\},\{0,2,3\},\{1,2,3\},\{0,1,1\},\{0,2,2\},\{0,3,3\},\{1,0,0\},\{1,2,2\},\{1,3,3\},\{2,0,0\},\{2,1,1\},\{2,3,3\},  
\{3,0,0\},\{3,1,1\},\{3,2,2\},\{0,0,0\},\{1,1,1\},\{2,2,2\},\{3,3,3\} 这些是合理的组合。

pku 1831 不定方程组(构造解)  
这个题目很有意思，说a1+a2..an=s,1/a1+1/a2....+1/an=1;求一组这样的解。  
为了找S的一组解，可以把S变小，来得到S的解。两种变小的方法:p/2+1/2=1 ,p\*2+2=S;或p/2+1/3+1/6=1,p\*2+9=S;选这两种方式是为了使奇数，偶数都有变小的方法。更重要的是当S一定大时，一定会有解。证明可以通过归纳来证得。所以事先保留一些小的S的解。大的S通过递归的构造出解来。

pku 2142 The Balance(不定方程)  
不定方程题，解a\*x+b\*y=d 。先求a\*x0+b\*y0=k。a/=k,b/=k,d/=k; 得到等价方程a'\*x+b'\*y=d'，一般解为x=x0-b'\*t,y=y0+a't;其中t为任意整数。

pku 2154 Color(波利亚定理,着色问题)  
一个经典的着色问题，题目描述的是一个正常的旋转群，它的轮换指标为1/n\*sigma(euler(d)\*(xd)^(n/d)) ，其中d为n的所有因子。有了这个生成函数就可以容的计算n种颜色，在正n边形上着色的不同方案数了。

pku 3352 In Danger(约瑟夫环)  
简单题，和具体数学第一章提到的问题是一样的，讲每数2去掉一人，求胜利人的编号。公式是  
f(n)=f(n/2)\*2-1 n=2\*k  
f(n)=f(n-1/2)\*2+1 n=2\*k+1

pku 2282 The Counting Problem(计数统计)  
一个计算问题，统计a,b之间0-9这些数字出现的次数。可以分别计算f(b),f(a-1)的大小,其中 a<b f(n)表示1到n数字出现的统计。对于f(n) ，可以按位计算，从个位到n的最高位，分别计算0-9的个数，0的计算有些特殊，因为0不能是一个数字的最高位  
while(a>=times)  
\{  
len=a/(times\*10);  
for(i=0;i<10;i++)aa\[i\]+=len\*times;  
if(len>0)aa\[0\]-=times;  
tmp=(a/times)%10;  
if(a>=times\*10)start=0;else start=1;  
for(i=start;i<tmp;i++)aa\[i\]+=times;  
aa\[tmp\]+=a%times+1;  
times\*=10;  
\}

pku 2429 gcd lcm Inverse  
大数分解，要分解的数很大，到了2^63,普通的素数表方法行不通，要使用Pollard分解，分解lcm/gcd。需要注意的是会出现lcm==gcd的情况。

pku 2769 Reduced ID Numbers(同余)  
给出n个数，找一个数p,使得没个数mod p的值不相等。即n个数mod p不同余。先求出任意两个数的差(要正的),找个最小的数，使其不是前面求的差的约数。

pku 2891 Strange Way to Express Integers(解模线性方程组)  
这题是解个同余方程组，既解x= ai (mod bi) ,题目没有保证bi之间两两互素，所以中国剩余定理，在这里没用。可以通过先求  
两个方程的解，这样就将两个方程和并成一个，直达只剩下一个为止就可以的到答案了。在合并的过程中有不能合并的情况出现就  
说明整个方程组没有解。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1\*x, a1+b1\*x= a2 (mod b2),用扩展欧几里德求出c。两个方程就  
可以用 c'= c (mod lcm(b1,b2))表示。  
hdu 1792 A New Change Problem  
题是说：给两个互质的数，要求出两个数所不能组合出的正整数。在较大数的每一个等价类中找出最小的一数，它是较小数的倍数，那么在这个等价类中小于这个数的都是不能被表示出来的。最大的一个不能被表示出来的数是(n-1)\*m-n 其中n>m,由于n有n个等价类，一个类包含不可表示出的数是m-1,总是是(n-1)\*(m-1)/2

pku 2888 Magic Bracelet(带约束的着色问题)  
这题还是要用到波利亚定理，唯一的不同是计算矩阵的幂模，再求矩阵的迹。具体的推导就不知道是怎么来的。关于矩阵是指允许相邻的两种颜色之间有边，这就形成了个无向图。矩阵的n幂模，和快速幂乘的原理是一样的。

pku 2917 Diophantus of Alexandria(不定方程，因数分解)  
模拟下后发现，满足1/x+1/y=1/z的x，y是z的约数，并且x，y互素。统计x，y的对数再加1（x=z,y=z是特殊的一对）。  
后来看到讨论里有公式，(x-z)(y-z)=z^2,计算小于z，并是z^2的约数就是答案了。

pku2992 Divisors (组合数，因子个数)  
计算C(n,k)的因子个数,由于n很小，最大为431，所以可以把1～431的所有数先因式分解，再来统计n\*(n-1)...(n-k+1)/k\*(k-1)...1的素因子个数。

pku 3370 Halloween treats(鸽巢原理)  
给定m个整数a1,a2,a3,..,am,存在整数k和l，0<=k<l<=m,使得ak+1 + ak+2 + ... +al能够被m整除。也就是说存在连续的一段al,...am,之和被m整除。考虑从a1...ai的和si，必定有si%m==0 或 si = sj (mod m),这种情况下取ai+1...aj,这段之和会是m的倍数。

pku 3128 Leonardo's Notebook(置换)  
题目意思是：一个置换是否可以由另一个置换的平方得来的。一个置换的平方，原来偶数长的循环会被分裂成两段长度相等的循环，而奇数长的循环不会被分裂。题目只是问是否存在，所以只要看所给置换中偶数长的循环是否成对，否则就不能由一个置换的平方得来。

pku 3244 Difference between Triplets(公式变形)  
很巧妙的公式变形，可惜不自己想出来的。首先计算max(a,b,c)-min(a,b,c)=(|a-b|+|b-c|+|a-c|)/2,有了这个公式就可以把比较变成加。那么  
D(Ta, Tb) = max \{Ia − Ib, Ja − Jb, Ka − Kb\} − min \{Ia − Ib, Ja − Jb, Ka − Kb\}  
=(|Ia-Ib-Ja+Jb|+|Ja-Jb-Ka+Kb|+|Ia-Ib-Ka+Kb|)/2  
令Ia-Ja=Wa,Ja-Ka=Ua,Ia-Ka=Ha;  
=(|Wa-Wb|+|Ua-Ub|+|Ha-Hb|)  
将读入的数据转化W,U，H三个数组，分别计算这三个数组任意两个元素的差的绝对值之和。这里要用小于O(n^2)的算法，把数组排序后可以拿掉绝对值，统计每个元素作为减数出现的次数。

pku 3324 Lucas-Lehmer Test(模运算)  
首先要用到高精度，用java很方便。在计算模的时候，由于是mod 2^p-1,可以用移位来加速。  
a=r (mod 2^p-1) => a=k\*(2^p-1)+r,先算个打概的k,得到的r>2^p-1,继续减2^p-1。这样比直接模运算要快。  
  
pku 3372 Candy Distribution(二次剩余系)  
根据题目的意思可以得到方程 1+n(n+1)/2 =a (mod N),显然这是一个二次模方程。要看N的二次完全剩余系是否都有解。  
结论是N要是2^x,x>=0,结论的证明还不知道。

pku 3516 Hide That Number（高精度）  
题目是说给出一个数y，找到 x\*11= y (mod 10^length(y)),如果y很小，直接求出逆来就能得到答案了，可是y很大，构造的方法没有想到，最后还是暴力做的。每次在y的前面加个数学(1,2..9),或是加上10这两个数字，看新得到的数字是11的倍数。若是，就可以得到答案了。由于y很大，普通的高精度会超时，要增加进制。

pku 3847 The Stable Marriage Problem（稳定婚姻）  
稳定婚姻问题。用到了延迟认可算法。用最优方提出匹配，而被匹配者，不会立即接受，而是在提出要求者的集合中去掉，比当前着差的元素，知道没有人提出匹配，被匹配者才确定下匹配关系。值得一提的是，稳定婚姻的存在性不能被保证。

pku 3358 Period of an Infinite Binary Expansion(数论，欧拉定理)  
这个题目是求两个数相除p/q，结果的小数部分用二进制表示，当q不是2的幂时，这个二进制是个无线循环的01串。  
下面是个模拟小数部分按二进制表示，可以发现二进制传一定会有循环，因为p=p%q,既然是循环，又是模运行，这和p模q的阶有关，p%q的阶一定是q的欧拉函数的因子。这样转换成一个模方程:p\*2^n = x(mod q),当然p和q要互素，2和q互素。在计算前把q中的2去掉，p，q同除最大公因数。然后从1开始枚举，所以的欧拉数的因子。

\#include <stdio.h>  
\#define pr printf  
int main()  
\{  
int i,p,q;  
while(scanf("%d%d",&p,&q)==2)\{  
pr("0.");  
for(i=1;i<=100;i++)  
\{  
p\*=2;  
pr("%d",p/q);  
p=p%q;  
\}  
pr("/n");  
\}  
\}  
/\*  
5 192  
0.000001101010101010101010101010101010101010101010101010101010101010101010101010  
1010101010101010101010  
\*/  
pku 3590 The shuffle Problem(置换，数的分解)

题目求一个排列通过置换之后再回到原来的那个排列，对于给定的排列求出一个满足置换次数最多的一个置换。一个置换可以分解成多个循环，每次置换元素之和在同一个循环中的元素发生转换，同一个循环中循环节是元素的个数，所以这个题是要把一个数分成多个数的和，让这些数的最小公倍数最大。要保证lcd最大应该分解出来的每个数两两互素。由于数比较小，23是能最大的素数，所以直接枚举可以满足。

pku 3641 Pseudoprime numbers(费马定理，快速幂乘)  
简单题，先看p是否是素数，若是直接输出no。否则计算(a^p)%p,若结果是a输出yes，否则输出no。

2008哈尔滨赛区网络预选1007 The Luckiest number（欧拉定理运用）  
题目说要找个数t，它的数字全是8，对于给定的n，t要是n的整数倍，求最小的t。  
赛后才发现这题并不拿，可能是我太菜了。这题问题可以转换成8\*(10^x-1)/9 = 0 (mod n ),这样就可以看出还有因子5和16的n是没有解的。并且n是偶数时，其解是n除去2因子的解。最后就是求解 10^x = 1 (mod 9\*n) n是一个奇数，所以(10,n)=1,这样就可以根据欧拉定理 ,满足等式的解只能是 euler(9\*n)的因子。枚举欧拉数的因子，最小的那个就是要求的解。由于n可以到2000000000，快速幂乘要支持64位运算。

2008 成都网络预选 1005 Farey Sequence Again(Farey Sequence ,构造)

与其说是数学题，还不如说是个模拟题。Farey Sequence序列规律性很强，暴力模拟后发现有很多规律。要用到的一个性质是

Fn中连续的3个元素，a1/b1 ,a2/b2,a3/b3。若a1+a3<n 并且 b1+b3<=n ,则 a2=a1+a3,b2=b1+b3。这个性质很有用，根据它可以推出序列中前n项的分子不超过3，而且在构造的时候也要用到这个性质，找个第一个分母是2和3的元素的位置，都可以通过观察看出规律。序列就分成了3段，第一段分子只有1，第二段分子有1和2，而且是2，1，2，1，2，。。。这样循环的。第三段有1，2，3，也会出现循环，或是3，1，3，2 或是3，2，3，1这样的循环结。所以的规律都可以在模拟的序列中看出。只有3为分子时看不出规律，但是这样的元素左右两个一定是分子为1和2的两个元素，根据性质，知道3周围的两个元素的分母，就可以得出分子为3的元素的分母

2008 哈尔滨现场赛 Simple Addition Expression hdu2451

通过读题发现满足要求的数字，最高位由1，2，3组成，最低位由0，1，2组成，中间由0，1，2，3组成。计算小于n的数有多少个这种数就是答案。

2008 哈尔滨现场赛 K-dimension number hdu2447

读题后发现K要么是p,要么是p^2 (p为素数)，且p<=97,K维数n的情况只有三种。

一，当k为p时，n=(p')^(p-1)

二，当k为p^2时，n=(p1')^(p-1)\*(p2')^(p-1)或n=(p1')^(p^2-1)

三，当k为1是，n=1。

zoj 2562 More Divisors(反素数，dp)

反素数是指在不大于n数中含有最多约数，值最小的一个，比如2，4，6。。都是反素数。题目要求在小于10^16中的反素数。

由于反素数要求约数尽量多，所以素因子个数要尽量少，而指数要尽量大，这样一个数成为反素数的机会就大。所以只要考虑前13个素数所能组成的数就可以。转移方程

f\[i\]\[j\]= min\{f\[i-1\]\[j/(k+1)\]\*p(i)^k\}

f\[i\]\[j\] 表示i个素数，有j个约数的最小值。p(i)表示第i个素数,j%(k+1)==0