HDU 4279 Number(找规律)

Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4288    Accepted Submission(s): 1066

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
 

题意: 给出一个f(x),表示不大于x的正整数里,不整除x且跟x有大于1的公约数的数的个数。定义F(x),为不大于x的正整数里,满足f(x)的值为奇数的数的个数。

题目就是求这个F(x)

题解:打个表找规律,F(x)=x/2-1+(sqrt(x)%2? 0:-1) 推荐证明:http://blog.csdn.net/acdreamers/article/details/9730423

注:sqrt()存在精度问题。精度处理不好会wa.

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define ll long long using namespace std; ll Sqrt(ll l,ll r,ll a) {
ll mid=(l+r)/2;
if(l>r)
return r;
if(a/mid>mid)
return Sqrt(mid+1,r,a);
else if(a/mid<mid)
return Sqrt(l,mid-1,a);
else
return mid;
} ll solve(ll r) {
if(r<6)return 0;
return r/2-2+(ll)Sqrt(1,r,r)%2;;
} int main() {
int t;
cin>>t;
while(t--) {
ll l,r;
scanf("%I64d%I64d",&l,&r);
printf("%I64d\n",solve(r)-solve(l-1));
}
return 0;
}
上一篇:hdu 4952 Number Transformation (找规律)


下一篇:HDU 5703 Desert (找规律)