تابع فی اویلر

نویسنده: ATofighi
ارسال‌شده در:
دیدگاه‌ها: 0

بسم الله الرحمن الرحیم

در کانال تلگرامی @dore_com سعی شده تا برخی از نکات مورد نیاز برای مرحله ۳ گفته شود. یکی از این نکات محاسبه تابع فی اویلر است.

تعریف:‌ \(\phi(n)\) تعداد اعداد ۱ تا \(n\) که نسبت به \(n\) اولند است.

مثلا \(\phi(1) = 1, \phi(2) = 1, \phi(6) = 2, \phi(8) = 4\) است.

در ادامه چند روش برای محاسبه‌ی \(\phi(n)\) و چند مثال برای آن ارائه خواهیم داد.

پیاده سازی با کمک اصل شمول و عدم شمول

اگر \(n = p_1^{q_1} \times p_2^{q_2} \times ... \times p_k ^ {q_k}\) باشد، که \(p_i\) عدد اول باشد. \(\phi(n)\) تعداد اعداد اولیست که بر هیچ کدام از \(p_i\) ها بخش‌پذیر نباشد و که این را می‌توان با کمک اصل شمول و عدم شمول محاسبه نمود:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 17;
int pr[N]; // pr[i] = maximum prime factor of i
int Phi[N];

vector<int> getPrimeFactors(int n) {
    vector<int> a;
    while(n > 1) {
		int x = pr[n];
		a.push_back(x);
		while(pr[n] == x) {
			n /= x;
		}
    }
    return a;
}

int phi(int n, vector<int> &p, int i = 0, int cnt = 0, int mul = 1) {
	if(i == p.size()) {
        if(cnt & 1) { // fard
			return -n/mul;
        }
        else {
			return n/mul;
        }
	}
	return phi(n, p, i+1, cnt, mul)+phi(n, p, i+1, cnt+1, mul*p[i]);
}

int phi(int n) {
	if(Phi[n]) return Phi[n];
	vector<int> p = getPrimeFactors(n);
	return Phi[n] = phi(n, p);
}

int main(){
	// set pr[i]
	for(int i = 2; i < N; i++) {
		if(pr[i] == 0) {
			for(int j = i; j < N; j += i) {
				pr[j] = i;
			}
		}
	}

}

این کد از نظر زمانی و حافظه اگر فی همه‌ی اعداد ۱ تا n را محاسبه کند از \(O(n \lg n)\) است.

یک تعمیم

می‌توان تابع فی را به شکل زیر تعمیم داد: \(g(n, m)\) تعداد اعداد ۱ تا n اند که نسبت به m اولند. با کمک رویکرد قبل می‌توان تابع جدید را نیز محاسبه نمود:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 17;
int pr[N]; // pr[i] = maximum prime factor of i

vector<int> getPrimeFactors(int n)
{
	vector<int> a;
	while(n > 1) {
		int x = pr[n];
		a.push_back(x);
		while(pr[n] == x) {
			n /= x;
		}
	}
	return a;
}

int g(int n, vector<int> &p, int i = 0, int cnt = 0, int mul = 1)
{
	if(i == p.size()) {
		if(cnt & 1) { // fard
			return -n/mul;
		} else {
			return n/mul;
		}
	}
	return g(n, p, i+1, cnt, mul)+g(n, p, i+1, cnt+1, mul*p[i]);
}

int g(int n, int m)
{
	vector<int> p = getPrimeFactors(n);
	return g(m, p);
}

int main()
{
	// set pr[i]
	for(int i = 2; i < N; i++) {
		if(pr[i] == 0) {
			for(int j = i; j < N; j += i) {
				pr[j] = i;
			}
		}
	}

}

که این کد از نظر زمانی و حافظه همانند کد قبل است.

پیاده سازی به کمک فرمول \(\sum_{d | n} \phi(d) = n\).

این یکی از فرمول‌های مهم مربوط به فی است و اثبات های متنوعی دارد. یکی از راه‌های اثبات آن به کمک دوگانه شماریست که پیشنهاد می‌کنم به آن فکر کنید.

خوب طبق این فرمول فی n را می‌توان n منهای فی مقسوم‌علیه‌های سره‌ی n حساب کرد. که جمع فی مقسوم علیه‌های سره را نیز می‌توان با کمک غربال اراتستن سریع محاسبه نمود.

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 17;
int phi[N]; // euler totient function

int main()
{
	for(int i = 1; i < N; i++) {
		phi[i] = i-phi[i];
		for(int j = i+i; j < N; j+= i) {
			phi[j] += phi[i];
		}
	}

}

این کد از نظر زمانی \(O(n \lg n)\) و از نظر حافظه \(O(n)\) است. اما کد قبل کمی سریعتر از این کد است.

پیاده سازی به کمک فرمول \(\phi(n) = n.\displaystyle\prod_{p|n} \left(1-\frac{1}{p}\right)\)

برای این محاسبه دوباره می‌توان از غربال اراتستن استفاده کرد، زیرا برای هر عدد تنها لازم است عوامل اولش را داشته باشیم و برای اینکه نیاز به استفاده از اعشار نداشته باشیم از روش زیر استفاده می‌کنیم:

اگر \(n = p_1^{q_1} \times p_2^{q_2} \times ... \times p_k ^ {q_k}\) باشد، \(\phi_i (n) = n \displaystyle\prod_{j=1}^i \left(1-\frac{1}{p_j}\right)\) ، که \(\phi(n) = \phi_k (n)\)، که این را می‌توان بازگشتی محاسبه کرد: \(\phi_0 (n) = n\) و برای \(i > 0\) : \(\phi_i(n) = \phi_{i-1} - \frac{\phi_{i-1}}{p_i}\) است.

که با کمک روش بالا می‌توان کدی ساده برای این فرمول ارائه داد:

// In the name of GOD
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 17;
int phi[N]; // euler totient function

int main()
{
	for(int i = 1; i < N; i++)
		phi[i] = i;
	for(int i = 2; i < N; i++)
		if(phi[i] == i) // i is prime
			for(int j = i; j < N; j += i)
				phi[j] -= phi[j]/i;
}

که این کد از نظر زمانی \(O(n \lg \lg n)\) و از نظر مموری \(O(n)\) است.

 

و این چیزهایی بود که من به خاطر داشتم و به نظرم مفید اومدند.

حال چند سوال که با کمک فی اویلر می‌توان آنرا حل کرد:

باسپاس و التماس دعا