BZOJ2190 & 欧拉函数

时间：2022-10-21 21:07:56

题意:

　　求1-n内互质数对个数

SOL:

　　裸欧拉函数,还有莫比乌斯反演的加速什么的,挖个坑.

Code:

　　

/*==========================================================================

# Last modified: 2016-03-16 20:57

# Filename: 2190.cpp

# Description:

==========================================================================*/

#define me AcrossTheSky

#include <cstdio>

#include <cmath>

#include <ctime>

#include <string>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm> 

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <vector> 

#define lowbit(x) (x)&(-x)

#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)

#define FORP(i,a,b) for(int i=(a);i<=(b);i++)

#define FORM(i,a,b) for(int i=(a);i>=(b);i--)

#define ls(a,b) (((a)+(b)) << 1)

#define rs(a,b) (((a)+(b)) >> 1)

#define getlc(a) ch[(a)][0]

#define getrc(a) ch[(a)][1] 

#define maxn 100000

#define maxm 100000

#define pi 3.1415926535898

#define _e 2.718281828459

#define INF 1070000000

using namespace std;

typedef long long ll;

typedef unsigned long long ull; 

template<class T> inline

void read(T& num) {

    bool start=false,neg=false;

    char c;

    num=0;

    while((c=getchar())!=EOF) {

        if(c=='-') start=neg=true;

        else if(c>='0' && c<='9') {

            start=true;

            num=num*10+c-'0';

        } else if(start) break;

    }

    if(neg) num=-num;

}

/*==================split line==================*/

ll ans=3;

int n,p[maxn],pri[maxn],ma[maxn];

void prepare(){

	memset(pri,false,sizeof(pri));

	for (int i=2;i*i<=n;i++)

		if (!pri[i])

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

				pri[j]=true,ma[j]=max(ma[j],i);

	FORP(i,2,n)

		if (!pri[i]) p[i]=i-1;

		else if (i/ma[i]%ma[i]==0) p[i]=p[i/ma[i]]*ma[i];

		else p[i]=p[i/ma[i]]*(ma[i]-1);

}

int main(){

	read(n); n--;

	prepare();

	FORP(i,1,n) ans+=p[i]*2;

	printf("%lld",ans);

}

相关文章