110 Dungeon 計(jì)算幾何：射線和球體相交
111 Very simple problem 二分枚舉
112 a^b-b^a 二分求冪 113 Nearly prime numbers 數(shù)論：素?cái)?shù)篩選
114 Telecasting station 枚舉115 Calendar 簡(jiǎn)單模擬116 Index of super-prime 動(dòng)態(tài)規(guī)劃：記憶化搜索117 Counting 二分求冪118 Digital Root 數(shù)學(xué)題119 Magic Pairs 數(shù)論：擴(kuò)展歐幾里得110 Dungeon 計(jì)算幾何：射線和球體相交
題意：給定一條3D射線 和 N個(gè)球體，問(wèn)射線的各種反彈經(jīng)過(guò)的球體編號(hào)，如果反射超過(guò)10次，只需要輸出前十次。
題解：很明顯，首先需要枚舉每個(gè)球體和當(dāng)前射線的相交情況，如果和多個(gè)球體相交肯定是取距離最近的球體進(jìn)行相交計(jì)算，然后計(jì)算出空間反射射線，重復(fù)以上操作11次，如果某次的反射射線已經(jīng)不能和任何球體相交那么直接跳出這個(gè)過(guò)程。
圖1
如圖1，表示射線AB和球O相交于B點(diǎn)，反射后的射線為BC，BD為球心O到交點(diǎn)的延長(zhǎng)線，那么必定滿足以下幾個(gè)條件：
已知A點(diǎn)坐標(biāo)(xa, ya, za)，單位向量tab
B點(diǎn)坐標(biāo) 為 (xb, yb, zb) = (xa, ya, za) + |AB| * tab (1)
B點(diǎn)在球O上，所以B點(diǎn)坐標(biāo)滿足
| (xb, yb, zb) - (xo, yo, zo) | = OB = Ro (2)
將(1)代入(2)，可計(jì)算出|AB|的長(zhǎng)度（由于是射線和球體求交，這兩個(gè)方程求出來(lái)的是直線和球體的交點(diǎn)，所以還需要計(jì)算方向判斷交點(diǎn)的可行性，如果交點(diǎn)有兩個(gè)，則取距離小的那個(gè)，如果只有一個(gè)交點(diǎn)，說(shuō)明是相切），然后利用(1)式計(jì)算出B點(diǎn)坐標(biāo)。
2) 射線經(jīng)過(guò)球體的反射射線
假設(shè)C點(diǎn)在A經(jīng)過(guò)B點(diǎn)反射后的反射射線上，并且AB = BC，那么AC必定和OB延長(zhǎng)線相交，假設(shè)交于D點(diǎn)；
單位向量cos(ABD) = Iba * Ibd；
BD = AB * cos(ABD)；
向量AD = 向量AB + 向量BD；
向量AC = 2 * AD；
點(diǎn)C (xc, yc, zc) = 向量AC + (xa, ya, za)；
向量BC求出后返回1) 繼續(xù)判斷和別的球的相交情況；
111 Very simple problem
二分答案 + 大數(shù)模擬
題意：給定X( X <= 10100)，求X開(kāi)方后的下取整。
題解：數(shù)組模擬大數(shù)。二分答案A，找滿足 A*A <= X 最大的A即為答案。
112 a^b-b^a
二分求冪 + 大數(shù)模擬
題意：求 ab - ba ( 0 < a, b < 100)。
題解：數(shù)組模擬大數(shù)。二分求 AB。
當(dāng) B == 0 則 AB = 1; 否則 AB = (A2)(B/2) * ( (B mod 2) ? A : 1 ); 遞歸求解。
113 Nearly prime numbers
素?cái)?shù)篩選 + 素?cái)?shù)判定
題意：判斷一個(gè)數(shù)是否為兩個(gè)素?cái)?shù)的積。
題解：利用傳統(tǒng)的素?cái)?shù)篩選將 1-31623 的素?cái)?shù)篩選出來(lái)，31623為平方大于等于109的最小整數(shù)，因?yàn)橐粋€(gè)數(shù)的開(kāi)方內(nèi)找不到一個(gè)(非1或它本身)因子的話它本身就是素?cái)?shù)，所以素?cái)?shù)只需要篩選到 109 的開(kāi)方 即可。
對(duì)于每個(gè)數(shù)，遍歷素?cái)?shù)數(shù)組，如果能被某個(gè)素?cái)?shù)整除，判斷商是不是一個(gè)素?cái)?shù)，如果商也是素?cái)?shù)結(jié)果為Yes，否則為No。
114 Telecasting station
枚舉 + 統(tǒng)計(jì)
題意：在X軸上規(guī)定一些有權(quán)值ai的點(diǎn) (x1,a1), (x1,a1), (x2,a2) .. (xn,an)要求在x坐標(biāo)上找到一個(gè)點(diǎn)X使得 M = |X-x1|*a1 + ... |X-xn|*an 的值最小。
題解：細(xì)心觀察可以發(fā)現(xiàn)，M是關(guān)于X的一次函數(shù)，所以可以確定X必定為 x1...xn中的某個(gè)點(diǎn)。
由于原式中存在絕對(duì)值，為了將絕對(duì)值化簡(jiǎn)，可以將X的區(qū)間分段，比如當(dāng)X 為 xj時(shí)可以簡(jiǎn)化為 M = (X-x1)*a1 + ...(X-xj)*aj + (xj+1-X)*aj+1 + ... + (xn-X)*an
= (X * presum[j] - preproduct[j]) + (postproduct[j+1] - X * postsum[j+1])
圖2
這些輔助數(shù)組可以通過(guò)四次線性掃描得出，復(fù)雜度O(n)。然后，先將xi遞增排序，枚舉每個(gè)xi，計(jì)算最小值更新M，就可以在O(n)的時(shí)間內(nèi)求解了。總體算法復(fù)雜度為排序復(fù)雜度O(n log n)。
115 Calendar
簡(jiǎn)單模擬
題意：給定一個(gè)月份M和天數(shù)N，求2001的那一天是星期幾。
題解：可以預(yù)處理出每個(gè)月的天數(shù)，如果天數(shù)大于那個(gè)月對(duì)應(yīng)的天數(shù)或者月數(shù)大于12肯定是不可行的，否則將給定月數(shù)M之前的 1到M-1個(gè)月的天數(shù)相加再加上N得到Sum，Sum mod 7就可以定位到星期幾了。
116 Index of super-prime
素?cái)?shù)篩選 + 記憶化搜索(或 動(dòng)態(tài)規(guī)劃)
題意：超級(jí)素?cái)?shù)是素?cái)?shù)下標(biāo)也是素?cái)?shù)的數(shù)，給定一個(gè)數(shù)N，問(wèn)這個(gè)數(shù)能不能被一些超級(jí)素?cái)?shù)組合出來(lái)，如果可以，需要滿足超級(jí)素?cái)?shù)的個(gè)數(shù)最少，要求輸出一個(gè)方案。
題解：先將滿足條件的 超級(jí)素?cái)?shù) 篩選出來(lái)，3 5 11 17等等，然后對(duì)于輸入的N進(jìn)行一次記憶化搜索（DP）
例如 N = 15
那么N的最優(yōu)值一定是來(lái)自 15-3=12，
15-5=10， 15-11=4 這三個(gè)數(shù)，以此類(lèi)推，遞歸出口是N = 0，每次計(jì)算完N就將它保存下來(lái)，下次就不用重復(fù)計(jì)算了。
所以狀態(tài)轉(zhuǎn)移方程為：DP[i] =
min{ DP [ i - p ] , p 為超級(jí)素?cái)?shù) } + 1
因?yàn)樾枰敵鼋M合的序列，所以每次搜索，需要保存當(dāng)前最優(yōu)值的前驅(qū)結(jié)點(diǎn)，最后一次性輸出即可。
117 Counting 二分求余
題意：給定N(N < 10001)個(gè)數(shù)Ai，求其中AiM
是K的倍數(shù)的數(shù)的個(gè)數(shù)。
題解：對(duì)于ab mod c二分求解。當(dāng)
b == 0 則 ab mod c = 1 mod c; 否則 ab mod c = (A2)(B/2)
* ( (B%2) ? A : 1 ) mod c;
118 Digital Root 數(shù)學(xué)歸納法
題意：定義f(n) 為 n的所有數(shù)字的和. 如果 f(n) 是1位數(shù)字，那么它是n的 "digital root"，否則n的"digital root" 為 f(n) 的"digital root"。
給定數(shù)組Ai，求 A1*A2* … *AN + A1*A2*…*AN-1 + … + A1*A2 + A1 的"digital root"(N <= 1000)。
題解：定義d(n)為n的"digital root"，利用數(shù)學(xué)歸納法可證明(從N=1的情況網(wǎng)上遞推)：
1) d( A1*A2* … *AN ) = d( AN * d( A1*A2* … *AN-1 ) )
2) d(A1 + A2 ) = d( d(A1) +d(A2) )
利用這兩點(diǎn)，可以直接掃描A數(shù)組就可以計(jì)算出給定表達(dá)式的"digital root"了。
119 Magic Pairs 枚舉 + 擴(kuò)展歐幾里得
題意：對(duì)于所有的(X,Y)在滿足 (A0 * X + B0 * Y) % N = 0 (1) 的情況下,使得(A * X + B * Y) % N = 0 (2) 也成立, 求這樣的 (A, B)。
題解：首先求出A0、B0、N三者的GCD，最后算出來(lái)的答案需要乘上這個(gè)GCD。
(A0 * X + B0 * Y) = K * N (3) (K為整數(shù))
(A * X + B * Y) = K' * N (4) (K'為整數(shù))
X = (K*N - B0*Y) / A0
代入(4)式,可得
A*(K*N - B0*Y) + B*A0*Y = K'* N * A0 (5)
化簡(jiǎn)得 (6)
(B*A0 - A*B0) * Y = (K'*A0 - K*A) * N (6)
兩邊同時(shí)mod N
得 (B*A0 - A*B0) * Y % N = 0 (7)
由于Y為任意整數(shù)(即Y有可能和N互素), 所以必須滿足 (B*A0 - A*B0) % N = 0 (8)
可以化簡(jiǎn)為 (B*A0 - A*B0) = K'' * N (9) (K''為整數(shù))
A0 * B + N * (-K'') = A*B0 (10)
枚舉A的值，就可以把方程轉(zhuǎn)化成了 ax + by = c的形式，其中:
a = A0, b = N, c = A*B0
x = B, y = -K''
利用擴(kuò)展歐幾里得即可求得最小的滿足條件的x(即B)的值了。
最后的答案需要乘上 A0、B0、N 三者的GCD。