Sigma Function

题目

给定一个n<=1e12,求在n之前的正整数，有多少个约数之和为偶数。

分析

我在题目的公式上看了半天推不出结论来。此题十分适合打表观察规律，所以可以打表看看。
打表结果：

1 : odd
2 : odd
3 : even
4 : odd
5 : even
6 : even
7 : even
8 : odd
9 : odd
10 : even
11 : even
12 : even
13 : even
14 : even
15 : even
16 : odd
17 : even
18 : odd
19 : even
20 : even
21 : even
22 : even
23 : even
24 : even
25 : odd
26 : even
27 : even
28 : even
29 : even
30 : even
31 : even
32 : odd
33 : even
34 : even
35 : even
36 : odd
37 : even
38 : even
39 : even
40 : even
41 : even
42 : even
43 : even
44 : even
45 : even
46 : even
47 : even
48 : even
49 : odd
50 : odd
51 : even
52 : even
53 : even
54 : even
55 : even
56 : even

可以得出规律：约数之和的数，要么是平方数，要么除以2之后是个平方数.所以我们可以把满足这条件的统计出来，就是约数之和为奇数的个数。然后n-约数之和为奇数的个数就可以了。

AC代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
int T;
ll fun(ll x){
    ll res = 0;
    for(int i = 1;i<=x;i++){
        if(x%i == 0) res += i;
    }
    return res%2;
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
//    for(int i = 1;i<=1000;i++){ //打表
//        cout<<i<<" : ";
//        if(fun(i)) cout<<"odd"<<endl;
//        else cout<<"even"<<endl;
//    }
    cin>>T;
    int kase = 0;
    while(T--){
        ll n,odd = 0;
        scanf("%lld",&n);
        for(ll i = 1;i*i<=n;i++){
            odd++;
            if(2*i*i<=n){
                odd++;
            }
        }
        printf("Case %d: %lld\n",++kase,n-odd);
    }
    return 0;
}