HDU 4279 - Number

2012年天津賽區網賽的題目，想了好久，也沒能想出來

還是小傑思路敏捷，給我講解了一番，才讓我把這個題做出來

f（x）=x-phi（x）（1——x與x互素個數）-g（x）（x的因子個數）+1

其中g（x）為multiply（q（i）+1），x=multiply（p（i）^q（i））（p（i）為所有素因子）

打表可得，phi（x）只有x=2時為奇數，其余全為偶數，而f（2）=0，可以不予考慮

所以，f（x）為odd的時候，x和g（x）模2同余

1、當x為odd時，q（i）+1全為odd，即q（i）必為even，所以x必為odd的平方數

2、當x為even時，q（i）+1全為even，即q（i）必為odd，所以x即為所有even減去even的平方數

最終可得公式 F（0——x）=x/2-2+（x==odd的平方數）

#include <stdio.h>   
#include <math.h>   
#define LL long long   
  
LL solve(LL x)  
{  
    if(x<=5)return 0;  
    LL ou=x/2-2;  
    LL k=sqrt(x);  
    LL ans=(k-3+2)/2+ou-(k-4+2)/2;  
    return ans;  
}  
  
int main()  
{  
    int T;  
    LL x,y;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%I64d%I64d",&x,&y);  
        printf("%I64d\n",solve(y)-solve(x-1));  
    }  
  
    return 0;  
}