ARC125 B - Squares（数学）

目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

计算 (x^2-y=a) ，其中 (a) 为任意平方数，(1<=x,y<=n), 输出答案有多少种

State

(1<=n<=10^{12})

Input

10
10000000000

Output

8
52583544

Solution

由于 (n) 的数据范围，套路性的将式子转化为 ((x-a)(x+a)=y)，显然 ((x-a)<=(x+a))，而再通过一点点的观察 ((x-a)) 和 ((x+a)) 奇偶相同，筛出答案来就可以了

Code

ll go(ll x, int bit)
{
    ll ans = x / 2;
    if(bit) ans = x - ans;
    return ans;
}

ll calc(ll X)
{
    ll ans = 0;
    for(ll i = 1; i * i <= x; i ++){
        ll r = x / i;
        ans = (ans + (go(r, i % 2) - go(i - 1, i % 2)) % mod) % mod;
    }
    return ans;
}

signed main()
{
    //IOS;
    while(~ sll(n)){
        pll(calc(n));
    }
    //PAUSE;
    return 0;
}