- 浏览: 307478 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx 的解题报告
http://acm.fzu.edu.cn/problem.php?pid=1607
题意:求n平均分成m份(m>1),问有多少种分法,以及平均的分量最多可以达到多少?
多少种分法:
求n的因子的组合数即可,由于m>1所以【所有因子取0个的情况不包括】
例如:n中有3个素因子p1,2个素因子p2,p1可以取0个,1个,2个,3个【4种情况】,p2可以取0个,1个,2个【3种情况】,所以分法 = 4*3-1 = 11
平均达到最大值:
n/(n的最小素因子)
http://acm.fzu.edu.cn/problem.php?pid=1753
题意:求多个组合数的最大公约数
思路:求各组组合数的各个素因子个数,以少为主,因为要的是公约数嘛,最后乘起来即可
求N!里包含某素数因子p的个数,就可以这样求。
while(n>0)
{
x+=n/p;
n/=p;
}
不理解请看:求N!的素因子个数的一个例子:
http://972169909-qq-com.iteye.com/blog/1126188
另外推荐这题:http://poj.org/problem?id=2992
需要预处理求n!的各个素因子个数,因为n比较小,可以开数组预处理存放后再用
http://acm.fzu.edu.cn/problem.php?pid=1607
题意:求n平均分成m份(m>1),问有多少种分法,以及平均的分量最多可以达到多少?
多少种分法:
求n的因子的组合数即可,由于m>1所以【所有因子取0个的情况不包括】
例如:n中有3个素因子p1,2个素因子p2,p1可以取0个,1个,2个,3个【4种情况】,p2可以取0个,1个,2个【3种情况】,所以分法 = 4*3-1 = 11
平均达到最大值:
n/(n的最小素因子)
#include <iostream> using namespace std; #define M 1000005 int pf[M]; //pf[i]储存i的最大素因子 bool hash[M]; int main() { int i, j, n, k = 0, a, b, tp, q; bool flag; /******************素数筛法******************/ for (i = 2; i < M; i++) { if (!hash[i]) { pf[i] = i; for (j = i << 1; j < M; j += i) if (!hash[j]) hash[j] = true, pf[j] = i; } } /******************素数筛法******************/ while (~scanf ("%d", &n)) { flag = false; a = b = 1; while (n > 1) //将n进行素数分解 { tp = 1; q = pf[n]; //获取n的最大因子 while (n % q == 0) //求有多少个q因子 { n /= q; if (n > b) //b是拿到的最多的分量 b = n; tp++; } a *= tp; //简单组合数学 } printf ("%d %d\n", a-1, b); } return 0; }
http://acm.fzu.edu.cn/problem.php?pid=1753
题意:求多个组合数的最大公约数
思路:求各组组合数的各个素因子个数,以少为主,因为要的是公约数嘛,最后乘起来即可
求N!里包含某素数因子p的个数,就可以这样求。
while(n>0)
{
x+=n/p;
n/=p;
}
不理解请看:求N!的素因子个数的一个例子:
http://972169909-qq-com.iteye.com/blog/1126188
另外推荐这题:http://poj.org/problem?id=2992
需要预处理求n!的各个素因子个数,因为n比较小,可以开数组预处理存放后再用
#include <iostream> using namespace std; #define LL __int64 #define inf 0x3fffffff #define M 100005 int p[10005], num[M], ni[155], mi[155]; //num[i]表示所求中有多少个i因子 bool flag; int main() { LL ans; memset (num, 0, sizeof(num)); int i, j, k = 0, t, n, m, tp, count, mins; /***********素数筛法***********/ /**********M以内的素数存到p数组**********/ for (i = 2; i < M; i++) { if (!num[i]) { p[k++] = i; for (j = i << 1; j < M; j+=i) if (!num[j]) num[j] = 1; } } /**********M以内的素数存到p数组**********/ /***********素数筛法***********/ while (~scanf ("%d", &t)) { memset (num, -1, sizeof(num)); mins = inf; for (i = 0; i < t; i++) { scanf ("%d%d", ni+i, mi+i); if (mins > ni[i]) //这个是必须的,自己想! mins = ni[i]; } for (j = 0; j < t; j++) { n = ni[j]; m = mi[j]; for (i = 0; i < k; i++) { if (p[i] > mins) //必须的! break; count = 0; /*****n!中有多少个p[i]*****/ if (n >= p[i]) { tp = n; while (tp) { tp /= p[i]; count += tp; } } /*****m!中有多少个p[i]*****/ if (m >= p[i]) { tp = m; while (tp) { tp /= p[i]; count -= tp; //因为是分母,所以减 } } /*****(n-m)!中有多少个p[i]*****/ if (n - m >= p[i]) { tp = n - m; while (tp) { tp /= p[i]; count -= tp; } } /****得到的count就是该组合数中有多少个p[i]****/ if (num[p[i]] == -1 || count < num[p[i]]) num[p[i]] = count; } } ans = 1; for (i = 0; i < k; i++) { if (num[p[i]] <= 0) continue; for (j = 0; j < num[p[i]]; j++) ans *= p[i]; } printf ("%I64d\n", ans); } return 0; }
发表评论
-
HDU 4746 Mophues
2013-10-01 17:29 2969莫比乌斯函数完整定义的通俗表达: 1)莫比乌斯函数μ(n ... -
HDU 3221 Brute-force Algorithm
2013-05-04 13:31 1646/* * [题意] * 略 * [解题方法] ... -
UVA 10168 Summation of Four Primes
2013-02-14 21:48 1773/* * [题意] * 将一个数拆成四个素数的和, ... -
UVA 10139 Factovisors
2013-02-09 22:56 2094/* * [题意] * 判断n!是否能被m整除(n ... -
UVA 10104 Euclid Problem
2013-02-09 22:50 1460新手请进:扩展欧几里德入门 /* * ... -
UVA 10006 Carmichael Numbers
2013-02-08 08:27 2414/* * [题意] * 输入n,若满足如下两个条件 ... -
UVA 10110 Light, more light
2013-02-08 08:23 1394/* * [题意本质] * 输入n,如果n的约 ... -
【polya+Euler】HDU 2239 机器人的项链
2012-08-20 13:06 1409KIDx的解题报告 题目 ... -
HDU 1979 Fill the blanks
2012-08-20 12:40 1070KIDx的解题报告 题目链接:http://ac ... -
【生成树计数】HDU 4305 Lightning
2012-08-16 15:45 2618KIDx的解题报告 题 ... -
【扩展欧几里德】SGU 106
2012-05-22 23:57 2270KIDx的解题报告 题目链接:http://acm.s ... -
【数论+容斥】POJ 1091 跳蚤
2012-05-17 13:11 3229KIDx的解题报告 题目链接:http://poj.o ... -
【数论法求一堆数的最小公倍数,结果高达几千位】LOJ 1024 Eid
2012-02-10 16:22 1776KIDx的解题报告 题意:求n个数的最小公倍数,结果很大 ... -
【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
2012-01-14 12:57 2220KIDx 的解题报告 题目链接:http://ligh ... -
【快速幂取模】fzu 1752 A^B mod C
2011-11-25 23:32 3631KIDx 的解题报告 参考《算法艺术与信息学竞赛》: 题目 ... -
【高次幂取模的应用】HDU 3609 Up-up
2011-11-25 22:42 2243KIDx 的解题报告 题目很容易看懂:http://acm.h ... -
模线性方程组-非互质中国剩余定理 (更新于2012/5/18)
2011-11-18 19:03 4625KIDx 的解题报告 该专题必备知识:解模线性方程 http: ... -
HDU 1410 PK武林盟主
2011-10-02 16:28 1092KIDx 的解题报告 题目链接: http://acm.h ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2537KIDx 的解题报告 http://acm.hdu.ed ... -
【提取素因子+积性函数】小明的密钥
2011-08-23 15:48 963http://acm.nyist.net/JudgeO ...
相关推荐
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
2021FZU计算机视觉期末复习
2021FZU计算机视觉作业(八)
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
fzu大数据基础实验4
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
这是关于我们飞跃手册项目的相关文档,包括成员分组信息表格,各组成员任务概要文档,项目日记等文档。 (This is a collection of documents relating to our Leapfrog Handbook project, including member ...
2011 ACM 多校联合 2011 MU11 13 FZU
FZU2021计算机视觉答案(三)
FZU2021计算机视觉答案(四)
2021FZU计算机视觉答案(五)
2021FZU计算机视觉答案(二 )
2021FZU计算机视觉答案(六)
ACM数学_FZU...............绝密..........