找规律 $O(1)$

$数学问题，答案肯定满足某种规律，简单的规律可以通过前几项直接看出来，复杂的需要推导$

/*
    实在看不出来就打表
*/
#include <iostream>
#include <set>

using namespace std;
set<int> a;

int main(){
    for (int i = 0; i <= 10; i ++){
        for (int j = 0; j <= 10; j ++){
            int t = i * i - j * j;
            if (t > 0) a.insert(t);
        }
    }

    for (auto i : a){
        printf("%d ", i);
    }
    return 0;
}

output:

1 3 4 5 7 8 9 11 12 13 15 16 17 19 20 21 24 25 27 28 32 33 35 36 39 40 45 48 49 51 55 56 60 63 64 65 72 75 77 80 81 84 91 96 99 100 

$可以看出一定包含奇数项，同时也包含偶数项，但是偶数项都是4的倍数\\ 用一下前缀和的思想$

#include <cstdio>

using namespace std;

int l, r;

int getcnt(int x){
    return (x + 1) / 2 + x / 4;
}

int main(){
    scanf("%d%d", &l, &r);
    printf("%d\n", getcnt(r) - getcnt(l - 1));
    return 0;
}