UVa 10110

題目

http://domen111.github.io/UVa-Easy-Viewer/?10110

在一條走廊上有編號 $1$~$n$ 的電燈泡

有個人在這條走廊上來回走 $n$ 趟，第 $i$ 次出發會將編號為 $i$ 的倍數的電燈泡開關轉換一次(也就是 開 -> 關 關 -> 開)，而在走回來不會做任何事

請問來回走完 $n$ 趟之後，第 $n$ 顆電燈泡是亮的還是暗的? (一開始所有電燈泡都是關的)

想法

如果第 $n$ 個電燈泡是關的，那麼他一定被操作了 $2k$ 次 ($k \in \mathscr{R}$)

反過來說，如果第 $n$ 個電燈泡是開的，那麼他一定被操作了 $2k-1$ 次 ($k \in \mathscr{R}$)

那何時電燈泡會被操作呢?

只有在他的因數出現的時候會被操作到

那麼如果某數字有奇數個因數，則最後會是開的，反之是關的

任何數字 $p$ 的因數 $q$ 都會有相對應的數字 $r$ 使得 $p = qr$，並且 $r$ 也是 $p$ 的因數

如果說因數是奇數，那就表示最中間的因數 $q$ 找到相對應的數字也是 $q$，使得 $p = q*q$

發現到，當因數個數為奇數，也就是 $p$ 是完全平方數的時候第 $n$ 個燈泡會是亮的，反之是暗的

那麼，我們只需要做開根號的動作，去看看開根號後的值平方以及原本的數字是否相同即可

不過這裡要練習二分搜，所以就二分搜開根號吧

Code

//By Koios1143
#include<iostream>
using namespace std;
long long n, tmp;

void search(long long l, long long r, long long p){
	long long mid, res;
	while(l!=r){
		mid = (l+r)/2;
		res = mid*mid;
		if(res == p){
			cout<<"yes\n";
			return;
		}
		if(res < p) l = mid+1;
		else r = mid;
	}
	cout<<"no\n";
	return;
}

int main(){
	while(cin>>n && n){
		search(0, n+1, n);
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(1)$

每筆測資找到答案的時間複雜度為 $O(logn)$

每筆測資總時間複雜度為 $O(logn)$