题目链接:uva 10837 - A Research Problem
题目大意:给定一个phin,要求一个最小的n,欧拉函数n等于phin
解题思路:欧拉函数性质有,p为素数的话有phip=p−1;如果p和q互质的话有phip∗q=phip∗phiq
然后根据这样的性质,n=pk11(p1−1)∗pk22(p2−1)∗⋯∗pkii(pi−1),将所有的pi处理出来,暴力搜索维护最小值,虽然看上去复杂度非常高,但是因为对于垒乘来说,增长非常快,所以搜索范围大大被缩小了。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxp = 1e4;
const int INF = 0x3f3f3f3f;
int ans;
int np, vis[maxp+5], pri[maxp+5];
int nf, fact[maxp+5], v[maxp+5];
void prime_table (int n) {
np = 0;
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i * i; j <= n; j += i)
vis[j] = 1;
}
}
void get_fact (int n) {
nf = 0;
for (int i = 0; i < np && (pri[i]-1) * (pri[i]-1) <= n; i++) {
if (n % (pri[i]-1) == 0)
fact[nf++] = pri[i];
}
}
bool judge (int n) {
if (n == 2)
return true;
for (int i = 0; i < np && pri[i] * pri[i] <= n; i++)
if (n % pri[i] == 0)
return false;
for (int i = 0; i < nf; i++)
if (v[i] && fact[i] == n)
return false;
return true;
}
void dfs (int ret, int cur, int d) {
if (d == nf) {
if (judge(cur+1)) {
if (cur == 1)
cur = 0;
ans = min(ans, ret * (cur+1));
}
return;
}
dfs(ret, cur, d+1);
if (cur % (fact[d]-1) == 0) {
v[d] = 1;
ret *= fact[d];
cur /= (fact[d]-1);
while (true) {
dfs(ret, cur, d+1);
if (cur % fact[d])
return;
ret *= fact[d];
cur /= fact[d];
}
v[d] = 0;
}
}
int solve (int n) {
ans = INF;
get_fact(n);
memset(v, 0, sizeof(v));
dfs(1, n, 0);
return ans;
}
int main () {
prime_table(maxp);
int cas = 1, n;
while (scanf("%d", &n) == 1 && n) {
printf("Case %d: %d %d\n", cas++, n, solve(n));
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
20210225-东吴证券-长城汽车-601633-看好欧拉品牌崛起.pdf
算法-数论- 欧拉函数.rar
Euler_difference.txt+前向欧拉法+后向欧拉法+中心差分法+matlab程序
欧拉函数 C语言实现 #include "iostream" #include "math.h" #define maxsize 100 using namespace std; typedef struct node { int num; int total; }struct_num; struct_num a[maxsize]; int is_prime(int n)
图论- 图的遍历- 欧拉通路与欧拉回路问题.rar
第八讲-机器人动力学--牛顿-欧拉方程.ppt
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...
Maximum-Eulerian-Cycle-Decomposition-Problem:最大欧拉循环分解问题的实例
行业分类-设备装置-欧拉旋转定理演示教具.zip
长城汽车-601633-看好欧拉品牌崛起
算法-计算几何- 欧拉公式(包含源程序).rar
视频讲解欧拉定理和欧拉函数的证明。详细解释了证明简化剩余系的关系为什么要先证明完全剩余系的关系。以及欧拉函数的计算。
组合数学中经典定理 的实现 其中有: cayley定理 mobius 定理 欧拉函数 序数法 整数拆分等
大数据-算法-基于欧拉方法的超高速撞击程序研制及碎片云相分布数值模拟.pdf
winker-Euler梁-弯曲波_欧拉梁_传递矩阵法_声子晶体.zip
给出了欧拉函数的部分性质的证明
COMSOL 两相流 欧拉-欧拉 双流体模型
winker-Euler梁-弯曲波_欧拉梁_传递矩阵法_声子晶体_源码.zip