UVa 113 Power of Cryptography

想法：
　　在題目條件下，k^n與(k+1)^n的差異double的精度可以分辨的出來，因此直接對p開根號在四捨五入即可。

UVa 11538 Chess Queen

題意：
　　兩個Chess Queen在同一欄，或同一行，或同一對角線上表示為attacking position，給定a*b棋盤，問為attacking position的情況有幾種?

想法：
　　分成位在同一欄(直)，同一行(橫)，和同一對角線三種情況分開算，假設a為寬(橫的)，b為長(直的)，a必須<=b：

• 兩個棋子位在同一直線共有 a*C(b,2)*2!
• 位在同一橫線共有 b*C(a,2)*2!
• 位在對角線上可以自己畫圖觀察得到，對角線最長為a，且最長的共有(b-a+1)條，其他比a還短的對角線(長度2~a-1)都各有2條，記得對角線有左斜和右斜兩個方向。
  ....
  ....   4x5的棋盤 對角線最長為4，共2條
  ....
  ....
  ....
  因此可得 2(左斜右斜)*[(b-a+1)*C(a,2) + 2*(C(2,2)+C(3,2)+C(4,2)+...+C(a-1,2))]
  = 2*[(b-a+1)*C(a,2) + 2*C(a,3)]
• 把以上三式加起來即是答案

UVa 375 Inscribed Circles and Isosceles Triangles

題意：
　　求內切圓的圓周長總合，由於內切圓有無限多個，只要求到半徑0.000001為止。

                         

想法：
　　先求斜邊T，在透過三角型面積 T*R*2 + B*R = B*H 算得內切圓半徑R。一開始我Pi値直接使用3.14159265359，想說已經夠了，沒想到還不夠精確@_@，因此pi要使用2*arcsin(1)。

UVa 10014 Simple calculations

題目連結
想法：
a[i] = (a[i-1]+a[i+1])/2-c[i]，代入i値，左右兩式從1加到n，消除多餘項目後可得到：

• a[1]+a[n] = a[0]+a[n+1] - 2*(c[1]+...+c[n])

再從這個等式代入n値，左右兩式從1加到n，可得到

• (n+1)*a[1] = n*a[0] + a[n+1] - 2*[n*c[1] + (n-1)*c[2] + ... + 1*c[n]]

此時只剩下a[1]為未知數。

UVa 107 The Cat in the Hat

題目連結
題意：
　　一隻高度H的貓可以呼叫N個小貓幫手(N是我們要算的)，其每個小貓高度為 H*(1/(N+1))，每隻小貓可以在呼叫它的幫手N隻，身高為H*(1/(N+1))^2，一直下去，直到呼叫的小貓高度為1後，就不能再呼叫幫手了，因此這些高度為1的最矮的貓(worker cats)要把工作作完。
　　
　　現在題目給定兩個數：

• 第一個數為最高的貓(一開始只有一隻最高的貓)的高度H
• 第二個數為高度為1的貓(worker cats)的數量W，
• 求出沒有工作的貓的數量(全部-W)以及這些貓的身高總合。

想法：
　　首先最高的貓呼叫幫手後，產生N隻，高度為H*(1/(N+1))，我們假設呼叫k次直到身高為1後停止，可得出兩個等式：

• H * (1/(N+1))^k = 1
• N^k = W

因此解出N以及k後即可知道每次呼叫多少貓以及身高變為多少，將等式移項取log：

• k * log(N+1) = log(H)
• k * log(N) = log(W)

我們將第一式除以第二式消除k，然後使用binary search找出N値，接下來就能求出答案了。

UVa 10025 The ? 1 ? 2 ?....? n = k problem

想法：
　　可以先將k取絕對值，只考慮正數k，然後假設?都是+，也就是sum = +1+2+3+....+n，然後當sum > k時，將某些'+'變成'-'湊成k，可以發現把'+'變成'-'時，sum都是減掉偶數，例如Example，sum = +1+2+..+5 = 15，要湊成12，這時候把任一個數變號都是減掉偶數，因此奇數(15)減掉偶數不可能變成偶數(12)，所以要把sum往上加，直到sum為偶數為止(因為偶數-偶數=偶數)。
　　總結：sum = 1+2+3+..+n，如果k為偶數，sum為>=k的最小偶數(偶=偶-偶)；如果k為奇數，sum為>=k的最小奇數(奇=奇-偶)。

UVa 550 Mutiplying by Rotation

題意：
　　給定3個數(假設B,A,S)，B表示B進位，A表示被乘數的最低位數字，S表示乘數，也就是現在是xxxxxA * S，問符合 xxxxxA * S = Axxxxx則Axxxxx是幾位數?

想法：
　　可以解出xxxxx是多少，以題目example(179487)為例，B=10, A=7, S=4，可以從等式
abcde7 * 4 =
7abcde
發現，7*4=28，所以e=8，進位2，然後知道e以後，8*4+2=34，d=4，進位3，4*4+3=19，c=9，進位1，依此類推...。因此我們可以將每個位數算出來，迴圈終止條件為該位數==A且進位為0。

UVa 10392 Factoring Large Number

題意：質因數分解

想法：
　　因為題目說1000000以上的質因數最多只有1個，因此我們質數表只要建到1000000即可，建表時可以跳過2和3的倍數比較快速。

UVa 10061 How many zero's and how many digits

題意：
　　以B進位計算N!尾數有幾個0以及有幾個位數。

想法：

1. 位數部分比較簡單，如果要知道n有幾位數，直接log(10,n)+1，那如果n要換成B進位的話就取log(B,n)+1，而log的計算規則，log(B,N!) = log(B,1)+log(B,2)+......+log(B,N)。
2. 計算尾數有幾個0，對(N!)質因數分解，計算每個因數的數量，然後再看這些因數能夠湊成幾個B，例如B=20，那麼有2和5這兩個質因數能組成20，計算能夠湊成幾個，本題時間限制夠長，因此算因數的時候直接2~B枚舉即可。

UVa 408 Uniform Generator

想法：
　　本題要確定Step與Mod的最大公因數是否為1，如果不是互質，那麼一定會存在空隙，比如(10,12)，其產生為10,8,6,4,2,0,..，空隙為gcd(10,12)=2。

UVa 10110 Light, more light

本題連結
題意：
　　有個人管理一條走廊的燈泡，當走廊有'n'個燈泡，編號1~n，預設是關閉的，他會來回走n趟，第i趟他把編號能被i整除的燈泡開關切換，本題問編號n的燈泡最後是亮還是暗。

想法：
　　n只有在其因數的時候被切換，因此如果因數個數為偶數，那麼最後是暗的，反之如果為基數則為亮的，而只有能被開平方根的時候因數個數才會為奇數。

UVa 424 Integer Inquiry

本題連結
想法：
　　先不考慮進位與不夠減的情況，把每個位數都加起來，最後再處理進位或借位。

UVa 10494 If We Were a Child Again

本題連結
想法：
　　與直式除法一樣，一邊作商數，一邊作餘數，直到被除數的個位數為止。

UVa 11038 How many 0's?

題目連結
想法：
　　將問題簡化為求1~m 0的總數，以及1~n 0的總數，然後最後再相減。
　　求1~n 0的總數，要將n分別算每個位數0的個數，舉例如30324：

• 先從右邊第一位'4'開始，其左邊為3032，表示1~30320在"第一位"總共有3032*1=3032個0
• 換第二位數'2'，其左邊為303，表示總共有303*10(右邊有1位)=3030個0
• 再換第三位數也是一樣，30*100=3000個0，
• 注意第四位數為'0'，因此原本應該是3*1000，但第3個1000其實只到324而以，所以為2*1000+324+1=2325個0 (+1是因為別忘了0~324是325個)
• 最後一位'3'，它是最高位數，因此不會有0
• 所以總共為3032+3030+3000+2325=11387

因此，此演算法從最低位(i==1)開始到最高位(i==k)結束，如果第i位不為0，直接左邊數字x10^(i-1)，如果第i位為0，那麼(左邊數字-1)x10^(i-1)+右邊數字+1，最後把每位數的0總數加起來即可。

UVa 900 Brick Wall Pattern

本題連結

想法：
　　我們用－表示橫的磚塊，∣表示直的磚塊，而兩個直的∣∣可以換成兩個橫的＝，以長度為5舉例，一開始我們可以先假設都是直的∣∣∣∣∣，首先我們可以將兩塊直的換成橫的＝，注意現在兩塊橫的有２個空位，分別是左邊和右邊，然後我們剩下3個直的磚塊，因此把這３個直的放到２個空位的方式為Ｈ(2,3)=4。再將兩個直的換成兩塊橫的，變成＝＝，現在４塊橫的有３個空位，然後剩下１個直的，因此為H(3,1)=3，最後全部加起來就是答案了，1+H(2,3)+H(3,1)=8。
　　本題其實寫出排列組合的C函數就完成了，H(m,n)=C(m+n-1,n)，因此可以先去寫UVa 369是C的題目，而注意type要用long long int。