HDU6608 - Fansblog

HDU4133 - StrangeStandard

StrangeStandard   一道反素数的题目，求的是区间内的最大反素数。一开始做我是打表的(而且这表还不是自己打出来的),代码如下:

UVA294 - Divisors

Divisors   题意是说算一个区间内的因子数最大的数。网上题解大都是用的dfs，但我又不想写dfs······然后看了一下，区间长度最长才1e4，用质因数分解求出区间内每一个数的因子数然后用最朴素的方法找出答案应该也能过吧······事实证明真的可以，而且只用了40ms 2333333。   这里做个笔记，所谓质因数分解求因子数，指的是，对于一个数x,必定存在以下式子: x = (a1^p1)*(a2^p2)*(a3^p3)*(a4^p4)*···*(an^pn)(其中,a1,a2,···，an均为质数)   那么,x的因子个数则为: sum(x) = (1+p1)*(1+p2)*(1+p3)*(1+p4)*···*(1+pn)..

POJ2891 - Strange Way to Express Integers

Strange Way to Express Integers   拓展中国剩余定理的模板题，但我并看不懂模板OTZ(过段时间会补上个人理解，先把代码放这)

HDU1018 - Big Number

Big Number   直接套用stirling数的公式即可。关于strling数，可参考下图

拓展欧几里得算法

普通的欧几里得算法   这大概是最为人熟知的数论算法了吧，作用是求出gcd(a,b)，代码如下:

卢卡斯定理与中国剩余定理

卢卡斯定理   卢卡斯定理主要是用来求组合数取模，即C(n,m)%p。其适用范围是:组合数很大，但p又不是很大且p是素数的情况(10^6+3也算是“不很大”) 。卢卡斯定理可以表达为:

HDU5446-Unknown Treasure(卢卡斯定理，中国剩余定理)

题目链接:Unknown Treasure 这道题求得实际上是C(n,m)%M,M=p1·p2·p3···pk。又因为pi都是素数，故可用卢卡斯定理。但这里不可以直接用Lucas，因为Lucas的使用条件是“C(n,m)很大，但p不太大，同时p为素数”，而这里的M可能会很大。故我们可以先求C(n,m)%p1,C(n,m)%p2,C(n,m)%pk，然后再利用中国剩余定理得到最终答案。 代码如下: #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; //从n个苹果中挑出m个相互..

BZOJ4403-序列统计(组合数学，卢卡斯定理)

题目链接:序列统计   首先，L与R实际上是没太大意义的，因为我们需要的只是L和R之间含有多少个数，即R-L+1个数。其次，要注意一点，在一个序列中，数字是可以重复的。以样例中的2 4 5为例，符合要求的序列有{4},{5},{4,5},{4,4},{5,5}。事实上，问题可以转化为“有R-L+1个不同的盒子，若要将i(1<=i<=n)个相同的小球放进这些盒子里(某些盒子可以为空)，问对于所有的i，放法的总和是多少？”其中，不同的盒子代表着不同的数，在一个盒子中放入一个球，相当于选取一次该数字作为序列中的成员。再将问题抽象一下，即为“将i个小球划分成k堆(1<=k<=i)，问对于所有的i，划分方法的总和是多少？”对于这个问题，我们可以直接用C(m+n,n)求解(对于本题是C(seg..

HDU3037-Saving Beans(卢卡斯定理，组合数)

  题目链接：HDOJ-3037   这道题关键之处在于式子的推导，只要把式子推导出来了，就可以直接套用Lucas的模板，从而求出答案。那么，公式要怎么求呢？   首先，问题要求的是从n棵树中收集不超过m个果实(原本以为是将不多于m个果实放到n棵树中......这题目表达有问题啊！)。也就是说，问题其实是求方程x1+x2+x3+···+xn=m的非负整数解的个数。那么我们要怎求呢？   首先，如果是求正整数解的个数，那我们可以直接用最简单的隔板法，即C(m-1,n-1);但这里求的是非负整数解，也就是说x1，x2，···,xn中的一个或多个可以为0。这种情况下，我们仍可以用隔板法来计算。方法是，将求非负整数解这一个问题转化为求正整数解，也就是将每一个x(x1,x2,···,xm)都加上1，构造一个新的方程y..