首页 > 代码库 > 欧拉函数 & 【POJ】2478 Farey Sequence & 【HDU】2824 The Euler function

欧拉函数 & 【POJ】2478 Farey Sequence & 【HDU】2824 The Euler function

2024-07-25 11:41:37   217人阅读

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

http://acm.hdu.edu.cn/showproblem.php?pid=2824

欧拉函数模板裸题，有两种方法求出所有的欧拉函数，一是筛法，而是白书上的筛法。

首先看欧拉函数的性质：

  1. 欧拉函数是求小于n且和n互质(包括1)的正整数的个数。记为φ(n)。
  2. 欧拉定理：若a与n互质，那么有a^φ(n) ≡ 1(mod n),经常用于求乘法逆元。
  3. 若p是一个质数,那么φ(p) = p-1，注意φ(1) = 1。
  4. 欧拉函数是积性函数：（wikipedia：http://zh.wikipedia.org/wiki/%E7%A9%8D%E6%80%A7%E5%87%BD%E6%95%B8）
    1. 若m与n互质，那么φ(nm) = φ(n) * φ(m)。
    2. 若n = p^k且p为质数，那么φ(n) = p^k - p^(k-1) = p^(k-1) * (p-1)。
  5. 当n为奇数时，有φ(2*n) = φ(n)。

基于素数筛的求欧拉函数的重要依据：

设a是n的质因数

若(n%a == 0 && (n/a)%a == 0) 则 φ(n) = φ(n/a)*a; （性质4的1推出）

若(n%a == 0 && (n/a)%a != 0) 则 φ(n) = φ(n/a)*φ(a)。（性质4的2推出）

素数筛：

poj 2748：

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=1000005;bool isnotprime[N];int prime[N], phi[N], cnt;void init() {	phi[1]=1;	for1(i, 2, N-1) {		if(!isnotprime[i]) prime[++cnt]=i, phi[i]=i-1;		for(int j=1; j<=cnt && i*prime[j]<N; ++j) {			isnotprime[i*prime[j]]=1;			if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; }			else phi[i*prime[j]]=phi[i]*phi[prime[j]];		}	}}int main() {	init(); int n;	while(n=getint(), n) {		long long ans=0;		for1(i, 2, n) ans+=phi[i];		printf("%lld\n", ans);	}	return 0;}

 

hdu 2824：g++是I64d我也是醉了。。。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=3000015;bool isnotprime[N];int prime[N], phi[N], cnt;void init() {	phi[1]=1;	for1(i, 2, N-1) {		if(!isnotprime[i]) prime[++cnt]=i, phi[i]=i-1;		for(int j=1; j<=cnt && i*prime[j]<=N-1; ++j) {			int p=prime[j];			isnotprime[i*p]=1;			if(i%p==0) { phi[i*p]=phi[i]*p; break; }			else phi[i*p]=phi[i]*phi[p];		}	}}int main() {	int l, r; init();	while(~scanf("%d%d", &l, &r)) {		long long ans=0;		for1(i, l, r) ans+=phi[i];		printf("%I64d\n", ans);	}	return 0;}

 

还有一种筛法，不需要求素数。。。有待研究。复杂度比前一种多了两个log，是nloglogn的。。。orz。还是用线性的素数筛吧。。

 

欧拉函数 & 【POJ】2478 Farey Sequence & 【HDU】2824 The Euler function


联系
我们