怪数_牛客博客

题解：

考察点： 数学，打表找规律

易错点：

注意最好把 $a$ 和 $b$ 都开成long long类型，因为在计算的过程中有可能会爆 $int$

解法：打表找规律

这题第一眼看上去并没有什么神奇的数学结论可以一眼秒掉，但数据范围又这门大，很显然可以通过打表来找规律。于是对 $100$ 以内的小数据进行暴力

#include "bits/stdc++.h"
using namespace std;
int main()
{
    for(int i=1;i<=100;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            sum+=i/j;
        }
        if(sum%2==0){
            if(i%100==0) printf("%d\n",i);
            else printf("%d ",i);
        }
    }
    printf("\n");
    return 0;
}

整理结果后有如下结果

4 5 6 7 8 
16 17 18 19 20 21 22 23 24 
36 37 38 39 40 41 42 43 44 45 46 47 48 
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 
100

很显然可以从上表中观察出来，当 $i$ 为偶数时，位于区间 $[i^2,(i+1)^2)$ 内数全为满足要求的怪数。

有了这个结论之后，对于整数 $X$ ，就可以快速统计出 $[1,X]$ 内的怪数个数。设 $v=[\sqrt{X}]$ ，则对 $v$ 进行分类讨论。如果 $v$ 是奇数，则说明从 $v^2$ 一直到 $X$ 之后不可能再存在怪数。而前面的怪数个数 $\sum_{i=0}^{i=\frac{v-1}2}4\times i+1$ 。而如果 $v$ 是偶数，则说明后面从 $v^2$ 到 $X$ 还存在怪数，故结果应该是 $\sum_{i=0}^{i=\frac{v-1}2- 1}4\times i+1$ 最后还应该加上 $X-v^2+1$ 。最后的集过应该为 $[1,b]$ 区间内的个数，减去 $[1,a-1]$ 区间内的个数。

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL a,b;
LL solve(LL x){
    if(x<0) return 0;
    if(x==0) return 1;
    LL v=sqrt(x),s=0;
    if(v%2){
        return v*(v+1)/2;
    }else{
        LL t=v-1;
        s=t*(t+1)/2;
        s+=x-v*v+1;
    }
    return s;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",solve(b)-solve(a-1));
    return 0;
}