首页 > ACM题库 > HDU-杭电 > HDU 4279-Number-数论-[解题报告]HOJ
2015
05-23

HDU 4279-Number-数论-[解题报告]HOJ

Number

问题描述 :

  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.

输出:

  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.

样例输入:

2
1 1
1 10

样例输出:

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

题目:Number


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


网上很多方法就是打表找规律,已经谈不上是算法了。

这里我们可以来分析:


不整除x且跟x有大于1的公约数的数的个数 f(x)=x-约数个数-互质数个数+1 。


把x素因子分解,易知x的约数个数为(质数的幂+1)的累乘。所以若要使约数为奇数,充要条件是(质数的幂+1)都为奇

数,即质数的幂都为偶数。所以此时x必然是一个平方数。


综上,x为平方数,其约数个数为奇数;x为非平方数,其约数个数为偶数。


互质数个数,我们有欧拉函数。

这里用到一个结论:欧拉函数在n>2时,值都为偶数。

所以,

当x>2时:

若x为平方数,f(x)=x-奇-偶+1,要使f(x)为奇数,则x必为奇数;

若x为非平方数,f(x)=x-偶-偶+1,要使f(x)为奇数,则x必为偶数。 

当x=1或2时,f(x)=0.


综上,F(x)的值为[3,x]中,奇数平方数+偶数非平方数的个数和,即 偶数个数-偶数^2的个数+奇数^2的个数。

而偶数个数为 x/2-1,-1是为了把2减掉。偶数^2个数为 sqrt(x)/2,奇数^2个数为 ( sqrt(x)-(sqrt(x)/2) )-1,这里-1是为了把1减掉。


所以,化简后,F(x)=x/2-1+(sqrt(x)%2? 0:-1).

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

using namespace std;
typedef long long LL;

LL Solve(LL n)
{
    LL ans=0;
    if(n<6) return 0;
    ans+=n/2-2;
    if((LL)sqrt(1.0*n)&1) ans++;
    return ans;
}

int main()
{
    LL a,b,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        cout<<Solve(b)-Solve(a-1)<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acdreamers/article/details/9730423