HDU4279(2012年天津網絡賽---數論分析題)

題意： 給出一個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;
}