【数学推理】Sigma Function LightOJ - 1336

爱被打了一巴掌 2022-06-04 03:16 202阅读 0赞

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题目链接][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;
    }

[SouthEast]: /images/20220604/ec039ff66cd0434ea2a3afc0f4c71dea.png
[SouthEast 1]: /images/20220604/6497f2d2a7e544c2a7ded65aa3adb6a7.png
[SouthEast 2]: /images/20220604/e10bc48a7faa4c6494b40d7984e4bcee.png
[vjudge]: https://vjudge.net/problem/LightOJ-1336