網頁

2014年2月8日 星期六

UVa 10110 Light, more light

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

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