题解：P14663 [KenOI 2025] 倍数题
shenqiliang1008
·
·
题解
题目描述
链接
每组询问给定 $n$，求出 $1$ 到 $n$ 中所有**完全平方数**中，有多少个数是 $3$ 的倍数。
## 思路
如果 $k$ 是 $3$ 的倍数，则 $k^2$ 是 $3$ 的倍数。
对于 $1$ 到 $x$，有 $\lfloor \frac{x}{3} \rfloor$ 个 $3$ 的倍数，其中 $x = \lfloor \sqrt{n} \rfloor$。
结合以上两点便可写出代码。
## 代码
[记录](https://www.luogu.com.cn/record/252054990)
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
int T; cin >> T;
while (T--) {
int n; cin >> n;
int x = sqrt(n);
cout << x / 3 << "\n";
}
return 0;
}
```