首页 > 代码库 > HDU 4279 Number

HDU 4279 Number

转载请注明出处:http://blog.csdn.net/u012860063?viewmode=contents

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4279


<marquee width="600">
HDU集训队选拔赛地点:3教3楼机房,时间:5月10日(周六)12:00开始,请相互转告,谢谢~
百度之星编程大赛——您报名了吗? 
</marquee>

Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2936    Accepted Submission(s): 805


Problem Description
  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.
 

Input
  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
  Output the total number of real numbers.
 

Sample Input
2 1 1 1 10
 

Sample Output
0 4
Hint
For the second case, the real numbers are 6,8,9,10.
 

Source
2012 ACM/ICPC Asia Regional Tianjin Online
 

Recommend
liuyiding


代码如下:(用C++提交WA了无数次,用G++一遍过

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
//大于4,而且不是偶数的平方数的偶数是real number
//奇数的平方的奇数是real number
__int64 calc(__int64 n)//计算小于等于n的real number的个数
{
    if(n<=4)
		return 0;
    __int64 t=sqrt(n*1.0);
    __int64 ans=(n-4)/2;//大于4的偶数的个数
    if(t%2==0)
		return ans;
    else 
		return ans+1;
}
int main()
{
    int T;
    __int64 A,B;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&A,&B);
        printf("%I64d\n",calc(B)-calc(A-1));
    }
    return 0;
}