- 浏览: 118480 次
- 性别:
- 来自: 北京
最新评论
将n分解为几部分,使得这几部分的最小公倍数最大,显然分解开的各部分应该有p^k的形式,其中p是素数
因为n最大为100,所以直接枚举即可,不过别人有说只用前9个素数就行,我不知道怎么证明
因为n最大为100,所以直接枚举即可,不过别人有说只用前9个素数就行,我不知道怎么证明
#include <cstdio> #include <cstring> #include <algorithm> using std::sort; const int maxn = 105; bool isp[maxn]; int p[maxn], lp; void make() { memset(isp, true, sizeof(isp)); lp = 0; for (int i = 2; i < maxn; ++i) if (isp[i]) { p[lp++] = i; for (int j = i * i; j < maxn; j += i) isp[j] = false; } } int step[maxn], maxm, cycle[maxn], lc; void dfs(int remain, int k) { if (p[k] > remain) { int m = 1; for (int i = 0; i < k; ++i) if (step[i]) m *= step[i]; if (m > maxm) { maxm = m; lc = 0; for (int i = 0; i < k; ++i) if (step[i]) cycle[lc++] = step[i]; while (remain--) cycle[lc++] = 1; } } else { step[k] = 0; dfs(remain, k + 1); for (step[k] = p[k]; step[k] <= remain; step[k] *= p[k]) dfs(remain - step[k], k + 1); } } int main() { make(); int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); maxm = 1, lc = 0; if (n == 1) cycle[lc++] = 1; else dfs(n, 0); sort(cycle, cycle + lc); printf("%d", maxm); int k = 1, tmp; for (int i = 0; i < lc; ++i) { tmp = k++; for (int j = 1; j <= cycle[i] - 1; ++j) printf(" %d", k++); printf(" %d", tmp); } printf("\n"); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1155/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 840线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 851线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 888写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 972转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1190封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 798终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 602写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1139源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 804import java.util.*; import j ... -
整数划分
2010-10-07 10:38 841#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 981// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1050typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1134最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1295Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 777static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 880标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 849“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1041“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1006推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
pku acm 2752 Seek the Name, Seek the Fame代码 kmp算法。解题报告:http://blog.csdn.net/china8848
Codes of PKU_ACM OnlineJudge Problem
Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, ...
pku acm 1050 To the Max代码,有详细注释,动态规划
pku acm 1274 The Perfect Stall 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
pku部分题代码,不多,试一下怎么上传文件!
Despite the fact that many 3D human activity benchmarks being proposed, most existing action datasets focus on the action recognition tasks for the segmented videos. There is a lack of standard large-...
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
Pku acm 第1163题 The Triangle 代码,有详细的注释,动态规划
我写的解题报告,关于度限制生成树的 网址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1639<br>题目:Picnic Planning 来源:East Central North America 2000
pku1664源代码
PKU JudgeOnline FAQ 中文版 常见问题解答
Pku acm 第1887题 Testing the CATCHER 代码,有详细的注释,动态规划
8数码代码pku1077,300ms(哈希+广度搜索)
ppt word PKU 课件 五星级灰常强大
ACM代码 北大pku。 搞ACM的可以参考一下。代码还是挺规范的。有接近150道题目的代码。
PKU 2339 Rock, Scissors, Paper 源代码
有一些代码是pku上的,希望大家看后给我留言,看看我的代码那里有问题??
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848