ZOJ3334 Body Check

ZOJ 5月月賽題目。

大意是給了n個實數，代表了n個人需要完成身體檢的時間。有m個醫生為他們作身體檢查。一個人可以分開不同時段給不同醫生作身體檢查，唯獨是一個人不可以同一時間給多於一個醫生作身體檢查。另，醫院時刻也只能有這兩個情況﹕要麼m個醫生都在為不同的人作身體檢查，要麼就只有一個人在加班。問，最少需要多久能為所有人完成檢查？

首先，可以通過安排，使得工模式為「m位醫生工作 --> 一醫生工作」。如果一個人不可以分開時段給不同醫生檢查，可以得出問題的一種特例就是partition問題，是NP-Complete的。正因為可以任意分開時段，我們第一個想法就是直接取平均數。不過需要注意另一個限制「一個人不可以同一時間給多於一個醫生作身體檢查」。因為像5和5.1而m=2的話，雖然平均數是5.05，但是第二個人的0.1無法分拆成兩個不同時段。可以直接觀察得出，假若有一個需時大於平均數的話，剩出來的時間基本上無法放到任何平均數線之前，因為這位人本身已經獨佔了平均數線以前的時段。若然沒有這樣的問題的話，那麼我們必定可以安排所有人在平數時限前完成檢查。基於平均數本是最優的，所以我conjecture了這個算法﹕

為所有數取平均數，然後檢查每個數，若大於平均數，把多出的加到答案裡，然後把它們設為平均數，完成後重新再取平均數檢查；否則把平均數加到答案裡，並輸出答案。

一次AC。

Lucas Theorem

讀過組合或概率的朋友都知道從種互不相同的東西取種，有種不同的組合，或記作。此式可以寫成以下形式﹕

如果給出一個質數，問除的餘數是多少？


1878年Lucas提出以下定理﹕

當中
和

就是把和寫成進制，然後每一個位的對應系數求相同問題，再取積則成。
把這個問題的轉化有一個好處，就是當非常大的時候，而相對地小，利用Lucas定理運算同樣問題會快很多。剩下的問題就是求除的餘數是多少。把此式展開，

根據模運算，可以計算每分數除的餘數，然後取積除的餘數即可。
問題是，模運算對除的餘數不能直接用分子分母的方法取得。其中一個方法是用擴張輾轉相除法，另一個方法比較巧妙。因為是質數，根據費馬小定理，若與互質，可得以下公式﹕

利用模運算，可得﹕


當中
求除的餘數直接等價於求除的餘數。求可以利上式以時間求出。
由於 ，此問題可以在時間內求出。

延伸﹕因為對於任何系數和，都必然小於。所以當為質數，費馬小定理必然成立。如果當呢？我們可以直接取其餘數，再套入費馬小定理即可。注意當餘數等於表示不存在。

ICPC 2557 The Drunk Jailer

題意說給了N道門，某男會做如下事件N次﹕
在第i次中，把i, 2i, 3i. . . 的門做手腳。如果該門是鎖著的，他會解鎖；否則重新把它鎖上。
問，有多少道門是解鎖？假設一開始所有門都是鎖上的。

由於N少於100，故以簡單的枚舉即可通過。在這裡不妨給大家另一種解題思路。

想想第i道門會被某男遇上多少次呢？答案顯然是i的因數總數。
我們知道當門被遇上偶數次，門最後必然被鎖上。但，問何時才會遇上奇數遍？

若把N寫成a x b，肯定如果在第a會遇上次門，第b次會同樣遇上。
因為如此，除非a = b，否則門必然被訪問偶數遍。
得出結論﹕只有平方數的門才會被某男訪問奇數遍。

問題轉化成﹕給出N，問有多少平方數少於等於N。
輕鬆解決。