【数学推理】Sigma Function LightOJ

【数学推理】Sigma Function LightOJ - 1336

Think:
1知识点：数学推理
2题意：由算数分解定理可知，任何一个大于1的整数都可以分解为质因子相乘的格式( SouthEast )
定义: SouthEast 1
输入n(n<=1e12)，判断区间[1, n]有多少个数x的σ(x)为偶数
3思路：
（1）：求解区间[1,n]，即使以O(n)的时间复杂度枚举区间[1, n]也会超时，因此整个区间的暴力枚举方案排除
（2）：回到σ(x)的求解公式，经过观察我们可以发现，若其中相乘的一项或者多项为偶数，则σ(x)必定为偶数，也就是直接思考σ(x)为偶数的情况比较多，进而反面思考可以发现，若σ(x)为奇数，则其中相乘的每一项必定为奇数
1>若p等于2，则无论对应的e为多少，该项为奇数
2>其它素因子：
(p^(e+1)-1)/(p-1)=(p*(e+1)-p+p-1)/(p-1)=p*(p^e-1)/(p-1)+1=p*(1+p^1+p^2+..+p^(e-1))+1
当e为偶数时：
(1+p^1+p^2+..+p^(e-1))为偶数个奇数相加，结果为偶数
p*(1+p^1+p^2+..+p^(e-1))为奇数p乘以一个偶数，结果为偶数
p*(1+p^1+p^2+..+p^(e-1))+1为一个偶数加1，结果为奇数
故证得当e为偶数时，该项为奇数
当e为奇数时：
(1+p^1+p^2+..+p^(e-1))为奇数个奇数相加，结果为奇数
p*(1+p^1+p^2+..+p^(e-1))为奇数p乘以一个奇数，结果为奇数
p*(1+p^1+p^2+..+p^(e-1))+1为一个奇数加1，结果为偶数
故证得当e为奇数时，该项为偶数
综1>和2>可得知，当p等于2或者e为偶数时，该项为奇数
注： SouthEast 2
3>对题目中的公式进行进一步判断行化简，可得
若σ(x)为奇数，则σ(x) = 2^k0 * (3^(2*k1) * 5^(2*k2) * … * pn^(2*kn));
即:
若k0为偶数，则σ(x) = (num)^2
若k0为奇数，则σ(x) = 2*((num)^2)

vjudge题目链接

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(){
    int cas = 1, T;
    LL n;
    scanf("%d", &T);
    while(T--){
        scanf("%lld", &n);
        LL cnt = 0;
        for(LL i = 1; i*i <= n; i++){
            cnt++;
            if(i*i*(LL)2 <= n) cnt++;
        }
        printf("Case %d: %lld\n", cas++, n-cnt);
    }
    return 0;
}