数学基础专项（一）basic problems

UVa 11388：只要对gcd、lcm的性质了解就可以很快得出结果，如果l%g==0，直接输出g和l即可，否则输出-1。

UVa 11889：通过简单演算可知，如果c%a!=0，直接输出c/a；否则，令b=c/a，要不断将a除以a与b的gcd，直到a与b的gcd为1，然后b乘以a所除之数的乘积，即为结果。

UVa 10943：也是简单的计数问题，结果就是组合数C(n+k-1,k-1)=C(n+k-1,n)，可坑爹的是在怎样计算组合数，按定义求显然会溢出，然后我按公式C(n,k+1)/C(n,k)=(n-k)/(k+1)从C(n,0)开始递推，可是WA，一想原来是取模时会出错。最后，只能改用递推，利用公式C(n+1,k+1)=C(n,k)+C(n,k+1)可以通过类似DP的递推形式求得结果。边界条件是C(n,0)=C(n,n)=0。

UVa 10780：因为n很小，可以预处理一下把10000以内的素数先做出一张素数表。然后将n！和m因式分解，然后n！各因子的阶与m各因子的阶的商的最小值即为结果。

UVa 10892：这道题真是令人蛋碎……一开始各种尝试用排列组合做，结果各种WA。之后去UVa的论坛看到可以用暴力做，然后就先找出所有因子，然后两两求lcm，然后就无悬念TLE……后来发现遍历一遍找出所有因子实在太慢，所以改为先因式分解，设各质因子的阶分别为p1，p2，……pk，由排列组合易知因子总数为(p1+1)*(p2+1)……(pk+1)，然后遍历一遍就可以求出所有因子(相当于对每个因子编码，要先记录质因子及其阶数)，然后再暴力就行了。

UVa 11752：这道题判溢出比较令人纠结，去了UVa论坛才知道了解需要利用好math.h里的函数，对于每个底数，其最高的不溢出的阶数为ceil(64/(log(base)/log(2)))-1。然后枚举1到1<<16内的数，用set保存结果，最后一并输出就行了。

UVa 11076：这道题本来想枚举所有全排列，发现最坏情况复杂度接近12！，显然是难以实现的。然后发现每个位置上元素出现的几率是相等的，只要求出排列个数再乘上输入的平均值组合而成的n位数，就可以在近似常数时间内解决该问题。

UVa 11609：易得结果为sum{k*C(n,k)|1<=k<=n}，因为C(n,k)=C(n,n-k)，所以可以将原式转化为n/2*sum{C(n,k)|0<=k<=n}。由二项式定理，可将结果化简为n*2^n-1。然后递归的求幂的模，时间复杂度为O(logn)。

UVa 11461：不知道为什么lrj会把这道题归入数学，反正我是直接用树状数组的。

UVa 11489：一道很简单的博弈，统计3对输入数求模分别为0、1、2的个数，以及所有数的和。只要判断第一步即可，从第二步开始就只能取3的倍数了，通过3的倍数的个数的奇偶性就可求得结果。

LA 2756：就是找规律，在纸上写了半天……本来想打表的，发现模拟好烦，就直接算了。公式很简单：当n为偶数时，f(n)=(n/2)*(n/2-1)；当n为奇数时，f(n)=(n/2)*(n/2)。

LA 2911：就是贪心，让尽量多的xi为sqrt(a)，剩下的n个，组成n-1个-1/sqrt(a)和1个(n-1)/sqrt(a)最后一加就行了。精度貌似可以不用管，反正我没有四舍五入直接过了。

LA 2889：不难发现长度为n的回文数有9*10^((n-1)/2)个，先预处理一下每个长度最后一个数的编号，然后可以很快求出在长度n内的编号，然后就可以推出结果了。

总结：都是一些相当基础的题，但我还是不能都很快做出来，数学思维还有待提高。接下来就要相应的提高专项的水平了，首先就是计数和递推了。Fighting！

ps：题目均出自lrj训练指南的题目推荐