UVa 10837 A Research Problem 欧拉函数
2024-10-14 07:18:10
题意:
给你一个欧拉函数值 phi(n),问最小的n是多少。 phi(n) <= 100000000 , n <= 200000000
解题思路:
对于欧拉函数值可以写成
这里的k有可能是等于0的,所以不能直接将phi(n)分解质因子。但是可以知道(Pr - 1)是一定存在的,那就直接枚举素数,满足phi(n) % (Pr-1)的都加进去,然后对这些素数进行爆搜。。。说到底还是暴力啊。。。想不到什么巧妙的办法了,最后需要注意的是,一遍枚举完各个素数后phi(n)除后还剩now,现在要判断(now+1)是否为素数,还是保证这个素数前面没有访问过。具体实现过程见代码~
/* **********************************************
Author : JayYe
Created Time: 2013/9/25 0:00:42
File Name : JayYe.cpp
*********************************************** */ #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; const int maxp = 10000 + 10;
bool vis[maxp], done[222];
int pri[maxp], pnum, cur_p[555], cnt_p[555]; void get_prime(int n) {
vis[1] = 1;
for(int i = 2;i*i <= n; i++) if(!vis[i])
for(int j = i*i;j <= n;j += i) vis[j] = 1;
pnum = 0;
for(int i = 2;i <= n; i++) if(!vis[i])
pri[pnum++] = i;
} int tot, ans; void split(int n) {
tot = 0;
for(int i = 0;i < pnum && (pri[i]-1)*(pri[i]-1) <= n; i++) if(n % (pri[i]-1) == 0) {
cur_p[tot++] = pri[i];
}
} int judge(int n) {
if(n == 1) return n;
n++;
// 判断剩余的值 + 1是否为素数
for(int i = 0;i < pnum && pri[i]*pri[i] <= n; i++) if(n % pri[i] == 0)
return -1;
for(int i = 0;i < tot; i++) if(vis[i] && n == cur_p[i]) // 判断这个素数是否已访问过
return -1;
return n;
} //left表示当前的n的值,now表示phi(n)剩余值
void dfs(int left, int now, int c) {
if(c == tot) {
int ret = judge(now);
// printf("left = %d now = %d ret = %d\n", left, now, ret);
if(ret > 0)
ans = min(ans, left*ret);
return ;
}
dfs(left, now, c+1);
if(now % (cur_p[c]-1) == 0) {
vis[c] = 1;
left *= cur_p[c];
now /= cur_p[c] - 1;
while(true) {
dfs(left, now, c+1);
if(now % cur_p[c]) return ;
now /= cur_p[c]; left *= cur_p[c];
}
vis[c] = 0;
}
} void solve(int n) {
memset(done, false, sizeof(done));
ans = 2000000000;
split(n);
dfs(1, n, 0);
} int main() {
get_prime(10000);
int n, cas = 1;
while(scanf("%d", &n) != -1 && n) {
solve(n);
printf("Case %d: %d %d\n", cas++, n, ans);
}
return 0;
}
最新文章
- [IOS]JSPatch
- IOS网络第四天 -网络文件上传(0923略)
- 【jq】c#零基础学习之路(1)Hello World!
- 解决openssl: error while loading shared libraries: libssl.so.1.1: cannot open shared object file: No such file or directory错误
- k.NIO方式SSL通道流程
- 创建一个最简单的Linux随机启动服务
- linux 集群配置ssh无密码访问
- 二维码工具类 - QrcodeUtils.java
- 新闻web小酌
- Oracle 数据库 Database Express Edition 11g Release 2 (11.2) 错误解决集锦(安装方面)
- OCA读书笔记(17) - 移动数据
- Button MouseEvent颜色变化
- vim中的批量替换
- mysql insert插入时实现如果数据表中主键重复则更新,没有重复则插入的四种方法
- maven 禁止连接外网仓库
- [Swift]LeetCode461. 汉明距离 | Hamming Distance
- 数据库行转列、列转行,pivot透视多列
- lxml基础
- [No0000DD]C# StringEx 扩展字符串类 类封装
- Pandas 基础(1) - 初识及安装 yupyter