求1~n内全部数对（x,y）,gcd(x,y)=质数，的对数。

思路：用f[n]求出,含n的对数。最后用sum【n】求和。

对于gcd(x,y)=a(设x<=y,a是质数),则必有gcd(x/a,y/a)=1;所以我仅仅要枚举i（设i=y/a），再枚举全部质数

他们乘积的f[i*a]值包含i的欧拉函数值。

时间复杂度（n*质数个数）

#include<iostream>

#include<cstring>

using namespace std;

const int maxx=100010;

int mindiv[maxx+5],phi[maxx+5];

void genphi()                  //求出1~n内全部数的欧拉函数值

{

    for(int i=1; i<=maxx; i++)

    {

        mindiv[i]=i;

    }

    for(int i=2; i*i<=maxx; i++)      //筛法

    {

        if(mindiv[i]==i)

        {

            for(int j=i*i; j<=maxx; j+=i)

            {

                mindiv[j]=i;

            }

        }

    }

    phi[1]=1;

    for(int i=2; i<=maxx; i++)

    {

        phi[i]=phi[i/mindiv[i]];

        if((i/mindiv[i])%mindiv[i]==0)

        {

            phi[i]*=mindiv[i];

        }

              else

        {

            phi[i]*=mindiv[i]-1;

        }

    }

}

int pri[maxx+5];

int nump=0;  //素数个数

int pp[maxx+5];    //存素数

void  getp()

{

    for(int i=2;i<=maxx;i++)

    {

       while(i<=maxx&&pri[i])i++;

        pp[nump++]=i;

        for(int j=i*2;j<=maxx;j=j+i)

                pri[j]=1;

    }

}

long long f[maxx+5];

long long sum[maxx+5];

int main()

{

    getp();

   genphi();

    for(int i=1;i<=maxx;i++)     //  枚举每一个i。i=y/pp[j]()

    {

        for(int j=0;j<nump&&i*pp[j]<=maxx;j++)   //枚举全部质数

        {

            if(i!=1)                             //（a,b）(b,a)算俩次。

f[i*pp[j]]+=phi[i]*2;

           else  f[i*pp[j]]+=phi[i];

        }

    }

    long long tsum=0;

    for(int i=1;i<=maxx;i++)

   {

       tsum+=f[i];

       sum[i]=tsum;

   }

   int n;

   while(cin>>n)

   {

       cout<<sum[n]<<endl;

   }

}