hdu 4345 Permutation(数论+dp)
发布日期:2021-11-12 00:25:55
浏览次数:5
分类:技术文章
本文共 2006 字,大约阅读时间需要 6 分钟。
Permutation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 835 Accepted Submission(s): 493 Problem Description
There is an arrangement of N numbers and a permutation relation that alter one arrangement into another. For example, when N equals to 6 the arrangement is 123456 at first. The replacement relation is 312546 (indicate 1->2, 2->3, 3->1, 4->5, 5->4, 6->6, the relation is also an arrangement distinctly). After the first permutation, the arrangement will be 312546. And then it will be 231456. In this permutation relation (312546), the arrangement will be altered into the order 312546, 231456, 123546, 312456, 231546 and it will always go back to the beginning, so the length of the loop section of this permutation relation equals to 6. Your task is to calculate how many kinds of the length of this loop section in any permutation relations.
Input
Input contains multiple test cases. In each test cases the input only contains one integer indicates N. For all test cases, N<=1000.
Output
For each test case, output only one integer indicates the amount the length of the loop section in any permutation relations.
Sample Input
12310
Sample Output
12316
Author
HIT
Source
题意:
求和为n的一些数的最小公倍数有多少种。
题解:
循环节的长度为各独立置换环长度的最小公倍数。问题即求相加和为N的正整数的最小公倍数的可能数。由于1不影响最小公倍数,问题转化为相加小于等于N的若干正整数的最小公倍数的可能数。如果这些正整数包含大于一个质因子,只会使得正整数的和更大。因而问题再次转化为相加小于等于N的若干质数的最小公倍数的可能数。
记忆化搜索写法上面的参考题解有。
递推写法:
#include#include #include #include #include #include #include using namespace std;#define rep(i,a,n) for (int i=a;i =a;i--)#define pb push_back#define fi first#define se secondtypedef vector VI;typedef long long ll;typedef pair PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=1000+10;int prime[maxn];void init(){ for(int i=2;i i) continue; int p=prime[j]; while(i>=p) d[i][j]+=d[i-p][j-1],p*=prime[j]; } } int n; while(~scanf("%d",&n)) { printf("%lld\n",d[n][prime[0]]); } return 0;}
转载地址:https://blog.csdn.net/fouzhe/article/details/56495333 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月03日 09时08分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
有趣的句子
2019-04-28
每天一道 python 面试题 - Python中的元类(metaclass) 详细版本
2019-04-28
Scrapy(6)Item loader 加载器详解
2019-04-28
每日一道python面试题 - Python的实例,类和静态方法揭秘
2019-04-28
今日金融词汇---新股新债前面的N,是什么?
2019-04-28
每日一道python面试题 - Python的实例,类和静态方法揭秘
2019-04-28
原创专辑来了
2019-04-28
好好做好你喜欢做的事情,并且把它做好
2019-04-28
反馈不足
2019-04-28
人生永远没有太晚的开始
2019-04-28
python 周日福利来了
2019-04-28
状态模式
2019-04-28
跳表SkipList
2019-04-28
跳跃表(Skip list)原理与java实现
2019-04-28
Java 常见的 30 个误区与细节
2019-04-28
干货|基于 Spring Cloud 的微服务落地
2019-04-28
WEB攻击手段及防御第2篇-SQL注入
2019-04-28
WEB攻击手段及防御第3篇-CSRF
2019-04-28
WEB攻击手段及防御-扩展篇
2019-04-28
spring bean初始化及销毁你必须要掌握的回调方法。
2019-04-28