數學基礎專項（一）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訓練指南的題目推薦