bzoj 2818: Gcd 歐拉函數

2818: Gcd

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1633 Solved: 724
[Submit][Status]

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

Sample Output

HINT

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

Source

求gcd(x,y)==prime[k] 對數（1<=x,y<=n）

枚舉質數p，求gcd(x,y)==1, (1<=x,y<=n/p)

設sphi(k)表示gcd(x,y)==1,(1<=x,y<=k),那麼，可以通過幾何法推導出sphi(k)=phi(k)*2+sphi(k-1)

然後此題可解。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 11000000

#define MAXV MAXN*2

#define MAXE MAXV*2

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

inline int nextInt()

{

        char ch;

        int x=;

        bool flag=false;

        do

                ch=getchar(),flag=(ch=='-')?true:flag;

        while(ch<''||ch>'');

        do x=x*+ch-'';

        while (ch=getchar(),ch<='' && ch>='');

        return x*(flag?-:);

}

int n,m;

bool pflag[MAXN];

int prime[MAXN],topp=-;;

int phi[MAXN];

void init()

{

        int i,j,k;

        int x,y;

        phi[]=;

        for (i=;i<MAXN;i++)

        {

                if (!pflag[i])

                {

                        prime[++topp]=i;

                        phi[i]=i-;

                }

                for (j=;j<=topp && i*prime[j]<MAXN;j++)

                {

                        pflag[i*prime[j]]=true;

                        phi[i*prime[j]]=phi[i]*phi[prime[j]];

                        if (i%prime[j]==)

                        {

                                x=i;y=prime[j];

                                k=;

                                while (x%prime[j]==)

                                {

                                        x/=prime[j];

                                        y*=prime[j];

                                        k++;

                                }

                                if (x==)

                                {

                                        phi[i*prime[j]]=y-y/prime[j];

                                }else

                                {

                                        phi[i*prime[j]]=phi[x]*phi[y];

                                }

                                break;

                        }

                }

        }

}

qword sphi[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        int i,j,k;

        init();

        scanf("%d",&n);

        qword ans=;

        sphi[]=;

        for (i=;i<=n;i++)

                sphi[i]=sphi[i-]+phi[i]*;

        for (i=;i<=topp && prime[i]<=n;i++)

        {

                ans+=sphi[n/prime[i]];

        }

        printf(LL"\n",ans);

}

巴特西