【BZOJ 3642】Phi的反函数

http://www.lydsy.com/JudgeOnline/problem.php?id=3643

因为$$\varphi(n)=\prod_i p_i^{{k_i-1}(p_i-1),n=\prod_ip_i}{k_i}$$

直接根据这个式子暴搜即可。

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 1 << 16;

bool notp[N];

int prime[N], num = 0, ans;

void shai() {

	for (int i = 2; i < N; ++i) {

		if (!notp[i])

			prime[++num] = i;

		for(int j = 1; j <= num && prime[j] * i < N; ++j) {

			notp[i * prime[j]] = true;

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

				break;

		}

	}

}

int n;

bool zhi(int x) {

	for(int i = (int) sqrt(x); i >= 2; --i)

		if (x % i == 0) return false;

	return true;

}

ll dfs(int tmp, int k) {

	if (k == 1) return 1;

	ll ans = -1, t, bas;

	int m;

	for(int i = tmp; i <= num && prime[i] - 1 <= k; ++i)

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

			m = k / (prime[i] - 1); bas = prime[i];

			t = dfs(i + 1, m);

			if (t != -1 && (ans == -1 || ans > bas * t)) ans = bas * t;

			while (m % prime[i] == 0) {

				m /= prime[i], bas *= prime[i];

				t = dfs(i + 1, m);

				if (t != -1 && (ans == -1 || ans > bas * t)) ans = bas * t;

			}

		}

	if (k >= N && zhi(k + 1) && (ans == -1 || ans > 1ll + k))

		ans = 1ll + k;

	return ans > 2147483647 ? -1 : ans;

}

int main() {

	shai();

	scanf("%d", &n);

	printf("%lld\n", dfs(1, n));

	return 0;

}

巴特西

【BZOJ 3642】Phi的反函数

最新文章

热门文章