J 开关问题

Description:

• 有一排 \(n\) 个开关，初始时，均处于关闭状态，现在按 \(i=1,2,...,n\) 的顺序执行共 \(n\) 次操作：第 \(i\) 次操作时，翻转第 \(i\) 个、第 \(2i\) 个、...、第 \(⌊n/i⌋×i\) 个开关，即，把打开的关闭，把关闭的打开。问：最终处于关闭状态的开关有几个？

Hint

对于样例 \(n=6\)，初始时第 \(1\)~\(n\) 个开关状态分别为 \(0,0,0,0,0,0\)，执行操作如下：

翻转第 \(1\) 个、第 \(2\) 个、...、第 \(6\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,1,1,1,1,1\)

翻转第 \(2\) 个、第 \(4\) 个、第 \(6\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,0,1,0,1,0\)

翻转第 \(3\) 个、第 \(6\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,0,0,0,1,1\)

翻转第 \(4\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,0,0,1,1,1\)

翻转第 \(5\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,0,0,1,0,1\)

翻转第 \(6\) 个开关，此时第 \(1\)~\(n\) 个开关状态分别为 \(1,0,0,1,0,0\)

Constraints:

• \(1≤n≤10^8\)

Analysis:

• 对于每个开关 \(i\)，考虑它会翻转的次数，当 \(i\) 的因子被翻转时，\(i\) 也会因此翻转，故其翻转次数为其因子的个数。若 \(i\) 有偶数个因子，最终关闭； 若\(i\) 有奇数个因子，最终打开。
• 容易验证，当且仅当 \(i\) 是完全平方数时，\(i\) 有奇数个因子。
• 故只需统计 \(1-n\) 中完全平方数的个数（开关打开）

Solution:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll ans;

int main() {
	ll n; cin >> n;
	for(ll i=1;i*i<=n;i++) ans ++;
	cout << n - ans << endl;
	return 0;
}