题目描述

首先定义"special number"：

    如果对于一个数字B，存在一个数字A(0<A<=B),并同时满足 B%A=0 和 gcd(A,B) != 1 ，那么我们就说A是B的"special number"。

    再定义一个函数f(x)表示x的"special number"的数量。并且如果f(x)%2=1时，我们就称x为"real number"。

    现在给你两个数字x和y且1<=x<=y<=2^63-1，求再[x,y]区间内"real number"的数量。

分析：

看到范围后，这题第一眼就打表有木有，然后自己拿着数据去YY.......，然后就搞定。

然而就是挂掉了。最后发现竟然在开方这里。

赛后试了下，如果这样： ans = sqrt(n) 就过不了

如果改成：ans = sqrt((long double)n) 就过了

然后本人手贱又尝试了一下这个：ans = sqrt((double)n) 还是过不了

难道long double 和 double 不是一个东西 ?

unsigned long long  开方竟然会有精度损失 ?

迷也......

代码如下：

@Frosero

#include <iostream>

#include <cstdio>

#include <cmath>

#define INF 0x3f3f3f3f

using namespace std;

int T;

unsigned long long p,a,b,x,y;

unsigned long long how(unsigned long long n){

    unsigned long long ans,tmp;

    if(n < 6) return 0;

    ans = n / 2 - 2; tmp = sqrt((long double)n);

    if(tmp & 1) ans++;

    return ans;

}

int main(){

    scanf("%d",&T);

    while(T--){

        cin>>a>>b;

        y = how(b);  x = how(a-1);

        cout<<y - x<<endl;

    }

    return 0;

}