Here are two numbers A and B (0 < A <= B). If B cannot be divisible by A, and A and B are not co-prime numbers, we define A as a special number of B.
　　For each x, f(x) equals to the amount of x’s special numbers.
　　For example, f(6)=1, because 6 only have one special number which is 4. And f(12)=3, its special numbers are 8,9,10.
　　When f(x) is odd, we consider x as a real number.
　　Now given 2 integers x and y, your job is to calculate how many real numbers are between them.

　　In the first line there is an integer T (T <= 2000), indicates the number of test cases. Then T line follows, each line contains two integers x and y (1 <= x <= y <= 2^63-1) separated by a single space.

　　Output the total number of real numbers.

2
1 1
1 10

0
4

Hint
 For the second case, the real numbers are 6,8,9,10. 
 

2012 ACM/ICPC Asia Regional Tianjin Online

liuyiding

比赛的时候真是把神经绷得太紧了。

打表代码

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
using namespace std;
#define ll  __int64
ll a[110];
int main()
{
    a[1]=0;
    for(int i=2;i<=50;i++)
    {
        int count=0;
        for(int j=2;j<i;j++)
        {
            if(i%j==0) continue;
            bool flag=false;
            for(int k=2;k<j;k++)
            {
                if(j%k==0&&i%k==0)
                {
                    flag=true;break;
                }
            }
            if(flag&&(i%j!=0)) {
               // cout<<i<<" "<<j<<"*"<<endl;
                count++;
            }
        }
        if(count&1) a[i]=a[i-1]+1;
        else a[i]=a[i-1];
        cout<<i<<" "<<a[i]<<endl;
    }
}

规律：long long xx = (long long)sqrt(x * 1.0);    if(xx & 1)    {        return ((x - 4) >> 1) + 1;    }    else    {        return ((x - 4) >> 1);    }