紫书习题 10-18 UVa 10837 (欧拉函数变形）

这道题很巧妙，要把式子变一下

phi(n) = n * (1 - 1 / p1) * (1 - 1 / p2)……(1 - 1 / pr)

= n * ((p1-1) / p1) * ((p1-2) / p2) ……((pr-2) / pr)

= p1^k1 * p2^k2……pr^kr * ((p1-1) / p1) * ((p1-2) / p2) ……((pr-2) / pr)

= p1^(k1-1) * (p1-1) * p2^(k2-1) * (p2-1)……pr^(kr-1) * (pr-1)

因为幂可以为0，所以不能直接质因数分解，要枚举枚举p1-1

计算的过程中phi(n)第一次除以(pr-1),答案就乘以pr，后来 phi(n)每次都是除以pr

答案乘以pr。因为n = p1^k1 * p2^k2……pr^kr，而phi(n) = p1^(k1-1) * (p1-1) * p2^(k2-1) * (p2-1)……pr^(kr-1) * (pr-1)

很多博客没有把这里讲清楚。

另外素数表打到根号10的八次方，也就是一万就可以了，最后一个单独暴力判断，还要注意之前没有用过。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

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

using namespace std;

const int MAXN = 11234;

bool is_prime[MAXN], vis[MAXN];

vector<int> prime, g;

int ans;

void get_prime()

{

	memset(is_prime, true, sizeof(is_prime));

	is_prime[0] = is_prime[1] = false;

	REP(i, 2, MAXN)

	{

		if(is_prime[i]) prime.push_back(i);

		REP(j, 0, prime.size())

		{

			if(i * prime[j] > MAXN) break;

			is_prime[i * prime[j]] = false;

			if(i % prime[j] == 0) break;

		}

	}

}

void init(int n)

{

	ans = 2e9;

	g.clear();

	REP(i, 0, prime.size())

		if(n % (prime[i] - 1) == 0)

			g.push_back(prime[i]);

}

bool judge(int sum)

{

	REP(i, 0, prime.size())

	{

		if(prime[i] * prime[i] > sum) break;

		if(sum % prime[i] == 0) return false;

	}

	REP(i, 0, prime.size())

		if(vis[i] && prime[i] == sum)

			return false;

	return true;

}

void dfs(int p, int sum, int tot)

{

	if(p == prime.size())

	{

		if(sum == 1) ans = min(ans, tot);

		else if(judge(sum + 1))

			ans = min(ans, tot * (sum + 1));

		return;

	}

	dfs(p + 1, sum, tot);

	if(sum % (prime[p] - 1)) return;

	vis[p] = 1;

	sum /= prime[p] - 1;

	tot *= prime[p];

	dfs(p + 1, sum, tot);

	while(sum % prime[p] == 0)

	{

		sum /= prime[p];

		tot *= prime[p];

		dfs(p + 1, sum, tot);

	}

	vis[p] = 0;

}

int main()

{

	get_prime();

	int n, kase = 0;

	while(~scanf("%d", &n) && n)

	{

		init(n);

		memset(vis, 0, sizeof(vis));

		dfs(0, n, 1);

		printf("Case %d: %d %d\n", ++kase, n, ans);

	}

	return 0;

}

巴特西

紫书习题 10-18 UVa 10837 (欧拉函数变形）

最新文章

热门文章

巴特西

紫书 习题 10-18 UVa 10837 (欧拉函数变形）

最新文章

热门文章

紫书习题 10-18 UVa 10837 (欧拉函数变形）