HDU 4279 2012网络赛Number(数论 欧拉函数结论约数个数)

NumberTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2500 Accepted Submission(s): 692


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

21 11 10

Sample Output

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

Source2012 ACM/ICPC Asia Regional Tianjin Online
题目大意：题目先给你一个定义f(x)表示的是比<=x且不是x的约数并且与x互素的个数，如果f(x)为奇数，那么x可以算做特殊数，问你a~b之间有多少个特殊数。
解题思路：除了1之外，没有与x互素且是x的约数的数字。所以就好办了。f(x)=x-约数个数-互素个数+1. 由欧拉函数值得到，phi(x)为偶数(x>2)。而一个数的约数的个数是由它素数分解幂数决定的，比如x=e1^p1*e2^p2.....x的约数个数为(p1+1)*(p2+1)*(...)...那么如果x的约数个数为奇数，p1,p2,..必须都为偶数，那么x必须为平方数。
下面开始讨论f(x)为奇数的情况:1.x为奇数，约数个数需要为奇数，那么x为平方数。2.x为偶数，约数个数需要为偶数，那么x不为平方数。特殊的:f(1)=0,f(2)=0;
下面寻找1~x满足条件的情况:a.偶数个数为x/2-1,减去1是因为除去了偶数2b.偶数平方个数为sqrt(x)/2c.是奇数,又是平方数个数为sqrt(x)-sqrt(x/2)-1 //平方数-偶数的平方数-奇数1答案是a-b+c,得到x/2-2+sqrt(x)-sqrt(x)/2-sqrt(x)/2;可以sqrt(x)分奇偶讨论:res=x/2-2+sqrt(x)%2?1:0;
这个好像只有G++能A掉，用c++WA了无数次。。。
题目地址：Number
AC代码：

int gcd(int m,int n){    int t;    while(n)    {        t=m%n;        m=n;        n=t;    }    return m;}int main(){    int i,j;    int p[55];    p[0]=0;    for(i=1; i<=50; i++)    {        int cnt=0;        for(j=2; j<i; j++)            if(gcd(i,j)>1&&(i%j!=0))                cnt++;        if(cnt&1) p[i]=p[i-1]+1;        else p[i]=p[i-1];        cout<<i<<" "<<p[i]<<"  "<<(i-4)/2<<" "<<(int)sqrt(i*1.0)<<" "<<endl;    }    return 0;}