程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2478 Farey Sequence(基於素數篩法求歐拉函數)

poj 2478 Farey Sequence(基於素數篩法求歐拉函數)

編輯：C++入門知識

http://poj.org/problem?id=2478

求歐拉函數的模板。

初涉歐拉函數，先學一學它基本的性質。

1.歐拉函數是求小於n且和n互質(包括1)的正整數的個數。記為φ(n)。

2.歐拉定理：若a與n互質，那麼有a^φ(n) ≡ 1(mod n),經常用於求冪的模。

3.若p是一個質數,那麼φ(p) = p-1，注意φ(1) = 1。

4.歐拉函數是積性函數：

若m與n互質，那麼φ(nm) = φ(n) * φ(m)。

若n = p^k且p為質數，那麼φ(n) = p^k - p^(k-1) = p^(k-1) * (p-1)。

5.當n為奇數時，有φ(2*n) = φ(n)。

6.基於素數篩的求歐拉函數的重要依據：

設a是n的質因數，若(N%a == 0 && (N/a)%a == 0) 則 φ(N) = φ(N/a)*a; 若(N%a == 0 && (N/a)%a != 0) 則φ(N) = φ(N/a)*(a-1)。

該題就是基於性質六，在線性時間內求歐拉函數。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)

using namespace std;
const int maxn = 1000010;
const int INF = 0x3f3f3f3f;

int n;
LL num[maxn];

LL phi[maxn]; //對應φ(i)
int flag[maxn]; //flag[i] = 0說明i是素數，否則不是素數
int prime[maxn];//存素數

void get_phi()
{
	int i,j,k;
	memset(flag,0,sizeof(flag));
	phi[1] = 1;
	k = 0;

	for(i = 2; i <= maxn; i++)
	{
		if(!flag[i]) //i是素數
		{
			phi[i] = i-1;
			prime[++k] = i;
		}
		for(j = 1; j <= k && prime[j]*i <= maxn; j++)
		{
			flag[i*prime[j]] = 1;
			if(i % prime[j] == 0)
				phi[i*prime[j]] = phi[i] * prime[j];
			else phi[i*prime[j]] = phi[i] * (prime[j]-1);
		}
	}
}

int main()
{
	get_phi();
	num[1] = 0;
	for(int i = 2; i <= maxn; i++)
		num[i] = num[i-1] + phi[i];

	while(~scanf("%d",&n)&&n)
		printf("%lld\n",num[n]);

	return 0;
}

C++入門知識

DFS FZU 2107

DFS FZU 2107 Problem 2107 Hu

C++11新特性之 std::forward(完美轉發)

C++11新特性之 std::forward(完美轉發)

重建二叉樹_C++，二叉樹_c

重建二叉樹_C++，二叉樹_c一、題目背景　　給定一個二叉

hdu1452 Happy 2004

原題：http://acm.hdu.edu.cn/sh

關於qt5在win7下發布 & 打包，qt5win7下發布

關於qt5在win7下發布 & 打包，qt5win7

C++新特性右值引用移動構造函數

C++新特性右值引用移動構造函數 1、右ࠆ