学步园

题意：如果A不是B的因子，且A B不互质 则称A是B的特殊数　定义一函数f（x） 为x的特殊数的数量
若f（x）为奇数 则 x为real number 给x 和y 求x和y间的real number。

思路：只要算出[sqrt(x),sqrt(y）]间的偶数n1和奇数的个数n2，和[x,y]间偶数的个数n3
则ans = n3 - n1 + n2;

证明：任一个数n 有n = phi(n)+g(n)+f(n)
例如：n = 12
则phi（n） = 4 ，（这些数是：1 5 7 11);g(x) = 5 ，(2 3 4 6 12);f(x) = 3 ，(8 9
10);

所以 f（n) = n - phi(n) - g(n),又有当n>2时，phi（n）总为偶数
所以要判断f（n）是奇是偶 只要判断 n - g（n）就行了
有四种情况，n为奇，g（n）为奇or偶，n为偶，g（n）为奇or偶
有一规律 n可开方则g（n）为偶（这个总能想明白吧） 然后没了。。。。
注：phi（x）是欧拉函数，g（n）是n的因子数的数量，f（n)就是题目说的special number的数量

#include <stdio.h>
#include <math.h>

long long btw_odd_even(long long a, long long b,long long
even_or_odd) //计算a，b间偶数or奇数的个
{                                                                      
//数
    long long
ret = (b-a+1)/2;
    if(a
> b)
       
return 0;
    if((b-a+1)%2
&& a%2==even_or_odd)
       
ret++;
    return
ret;
}

int main()
{
    int t;
   
scanf("%d",&t);
   
while(t--)
    {
       
long long count = 0;
       
long long x, y;
       
long long rootx, rooty;
       
scanf("%I64d %I64d",&x,&y);
       
if(x <= 2)
           
x += 3;
       
rootx = (long long)ceil(sqrt(x));
       
rooty = (long long)sqrt(y);
       
count =  btw_odd_even(rootx,rooty,1)
               
-btw_odd_even(rootx,rooty,0)
               
+btw_odd_even(x,y,0);
       
printf("%I64d\n",count);
    }
    return
0;
}