LightOJ - 1336 Sigma Function（唯一分解定理，n以内平方数个数）

链接：LightOJ - 1336 Sigma Function

题意：

$\sigma (x)$表示$x$的所有因数之和，给出$n(1\le n\le 10^{12})$，问$1$ ~ $n$中有多少数的$\sigma$值是偶数？

分析：

根据唯一分解定理，有$x=p_1^{a_1}?p_2^{a_2}?p_k^{a_k}$

则 $\sigma (x)=(1+p_1+p_1^2+?+p_1^{a_1})(1+p_2+p_2^2+?+p_2^{a_2})?(1+p_k+p_k^2+?+p_k^{a_k})$

由于 奇数$\times$奇数$=$奇数$,$偶数$\times$奇数$=$偶数，所以我们可以 讨论$\sigma (x)$为奇数的情况，即 所有乘数均为奇数 的情况。

当$p=2$时，可以发现，无论$a$是多少，$(1+p+p^2+?+p^a)$都一定为奇数；

而当$p?=2$时（则质因数$p$一定是奇数），可以发现，仅当$a$为偶数的时候，$(1+p+p^2+?+p^a)$为奇数，否则为偶数。

然后，我们可以对质因数$2$的指数$a$进行讨论，若$a$是偶数，因为其他质因数的$a$也是偶数，所以这个数满足$k^2$
若$a$是奇数，同理，因为其他质因数的$a$是偶数，则这个数满足$2?k^2$

所以，我们只需要找到上述两种数的个数：

• $n$以内满足$k^2$的个数：$\sqrt{n}$（因为$1$ ~ $\sqrt{n}$的所有数平方后都在$n$以内）
• $n$以内满足$2?k^2$的个数：$\sqrt{\frac{n}{2}}$（因为$1$ ~ $\sqrt{\frac{n}{2}}$的所有数平方后乘以$2$都在$n$以内）

则最终答案为 $ans=n?\sqrt{n}?\sqrt{\frac{n}{2}}$

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
    int T,kase=0;scanf("%d",&T);while(T--){
    LL n,ans;scanf("%lld",&n);ans=n-(LL)sqrt(n)-(LL)sqrt(n/2);printf("Case %d: %lld\n",++kase,ans);}return 0;
}