BZOJ 2257: [Jsoi2009]瓶子和燃料 (裴蜀定理)

2257: [Jsoi2009]瓶子和燃料

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1246  Solved: 756
[Submit][Status][Discuss]

Description

jyy就一直想着尽快回地球,可惜他飞船的燃料不够了。
有一天他又去向火星人要燃料,这次火星人答应了,要jyy用飞船上的瓶子来换。jyy
的飞船上共有 N个瓶子(1<=N<=1000) ,经过协商,火星人只要其中的K 个 。 jyy
将 K个瓶子交给火星人之后,火星人用它们装一些燃料给 jyy。所有的瓶子都没有刻度,只
在瓶口标注了容量,第i个瓶子的容量为Vi(Vi 为整数,并且满足1<=Vi<=1000000000 ) 。
火星人比较吝啬,他们并不会把所有的瓶子都装满燃料。他们拿到瓶子后,会跑到燃料
库里鼓捣一通,弄出一小点燃料来交差。jyy当然知道他们会来这一手,于是事先了解了火
星人鼓捣的具体内容。火星人在燃料库里只会做如下的3种操作:1、将某个瓶子装满燃料;
2、将某个瓶子中的燃料全部倒回燃料库;3、将燃料从瓶子a倒向瓶子b,直到瓶子b满
或者瓶子a空。燃料倾倒过程中的损耗可以忽略。火星人拿出的燃料,当然是这些操作能
得到的最小正体积。
jyy知道,对于不同的瓶子组合,火星人可能会被迫给出不同体积的燃料。jyy希望找
到最优的瓶子组合,使得火星人给出尽量多的燃料。

Input

第1行:2个整数N,K,
第2..N 行:每行1个整数,第i+1 行的整数为Vi

Output

仅1行,一个整数,表示火星人给出燃料的最大值。

Sample Input

3 2
3
4
4

Sample Output

4

HINT

选择第2 个瓶子和第 个瓶子,火星人被迫会给出4 体积的容量。

思路:

思路完全错掉了orz…想去贪心来着….

因为自己脑算的例子错掉了…容量3和容量7的瓶子,能得到的最小是1不是2(因为忘了可以从瓶子中倒回燃料库的操作)…

样例一错毁所有orz..

正确的思路是,容量为a,b的两个瓶子能鼓捣出的体积一定是ax+by的形式

根据裴蜀定理,ax+by能得到的最小正数解就是(a,b),也就是gcd(a,b)

由此可以推广到多个瓶子,容量分别为x1,x2,…xn,能得到的最小体积就是gcd(x1,x2..xn)

(能推广的原因还是多说一句吧,假设现在只有两个瓶子x1,x2,称出了gcd(x1,x2),那么其实和只有一个容量为gcd(x1,x2)的瓶子在效果上是等价的)

因为剩下我们要做的就是,统计每个容量的因子统计,找到最大的并且出现此处大于等于k次的…

 

 

codeforces #382 div2 D. Taxes(哥德巴赫猜想)

题目链接

题意:一个人有n元前,他要交的税是n的最大因子(除n外),现在这个投机倒把者想把前分成k部分(k为大于等于1的任意值)每部分不能为1,分别交税,问最少交多少税。

思路:要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想

内容是:任何一个大于2的偶数可以写成两个素数的和。

(虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的2333

那么任何大于2的偶数,答案就是2

奇数可以分成一个3和一个偶数,答案为3.

不过这可能还不够优,这也是这道题的两个trick所在:

如果该数本身为素数,那么不用分(k取1),答案为1

如果该数减去2为素数,那么答案为2.

 

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接

题意:求一个楼梯数%m的大小。

思路:指数循环节。

需要注意的是,模数只有最外层是m,每往里一层,模数都变成m=phi(m)

所以可以写个dfs或者先预处理出每一层m存一下。

记得考虑n=1的特殊情况。

 

 

hdu 4704 Sum (隔板法,指数循环节,费马小定理)

题目链接

题意:定义s(k)为将n分成k个正整数的划分数,给出n,问s(1) + s(2) + … + s(n-1) + s(n)是多少,结果%1E9+7,其中n<=10^100000。

思路:首先化简要求的式子。

根据隔板法_维基百科

现在有10个球,要放进3个盒子里

●●●●●●●●●●

隔2个板子,把10个球被隔开成3个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、……

如此类推,10个球放进3个盒子的方法总数为{{\binom {10-1}{3-1}}={\binom {9}{2}}=36

n个球放进k个盒子的方法总数为{{\binom {n-1}{k-1}}

问题等价于求{x_{1}+x_{2}+...+x_{k}=n的可行解数,其中x_{1},x_{2},...,x_{k}正整数

 

于是问题转化成:

n个木棍,n-1个缝,

分成1份则是C(n-1,0);

分成2份则是C(n-1,1);

分成3份则是C(n-1,2);

分成n份则是C(n-1,n-1);

ans = sum( C(n-1,i) ) (0<=i<=n-1)

=2^(n-1);

 

这是我能理解的得到2^(n-1)的方式。。。

看到有好多人说这个结论是显然的。。。求指教(说这是个结论记住就好的就算了23333)

接下来,就是求A=2^(n-1)%1E9+7的问题了。。。

根据指数循环节公式A=2^((n-1)%(mod-1))*2^(mod-1)%mod (其中mod=1E9+7)

由于gcd(2,1E9+7)=1,根据费马小定理2^(mod-1)%mod=1,因此A=2^((n-1)%(mod-1))

然后快速幂搞之。

 

 

 

hdu 4549 M斐波那契数列 (矩阵快速幂+费马小定理+指数循环节)

题意:M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n,你能求出F[n]的值吗?

思路:观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))

此处要用到指数循环节的知识:

111qqz_指数循环节学习笔记

a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M))

然后 因为1000000007是质数,对于任意的x,有gcd(x,1000000007) = 1,所以可以结合费马小定理化简上式:

a^n ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m)

记得特判一下n为0和1的情况。

xiaodingli

 

poj 2891 Strange Way to Express Integers (扩展欧几里得算法解一般线性同余方程组)

题目链接

题意:给出k个方程,形式为 x%a1==r1,求最小的正数x,无解输出-1.

思路:首先很容易让人联想到crt.

然而crt的使用条件是,所有的m(也就是这道题中的a)两两互质,这道题并不满足,因此不能使用crt.

X mod m1=r1
X mod m2=r2



X mod mn=rn

首先,我们看两个式子的情况
X mod m1=r1……………………………………………………………(1)
X mod m2=r2……………………………………………………………(2)
则有
X=m1*k1+r1………………………………………………………………(*)
X=m2*k2+r2
那么 m1*k1+r1=m2*k2+r2
整理,得
m1*k1-m2*k2=r2-r1
令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
ax+by=m
熟悉吧?此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则方程无解。(理论依据:裴蜀定理
否则,继续往下。

解出(x,y),将k1=x反代回(*),得到X。
于是X就是这两个方程的一个特解,通解就是 X’=X+k*LCM(m1,m2)
这个式子再一变形,得 X’ mod LCM(m1,m2)=X
这个方程一出来,说明我们实现了(1)(2)两个方程的合并。
令 M=LCM(m1,m2),R=r2-r1 注意这里原博客写错了,应该为R=x*m1+r1
就可将合并后的方程记为 X mod M = R。

然后,扩展到n个方程。
用合并后的方程再来和其他的方程按这样的方式进行合并,最后就能只剩下一个方程 X mod M=R,其中 M=LCM(m1,m2,…,mn)。
那么,X便是原模线性方程组的一个特解,通解为 X’=X+k*M。

如果,要得到X的最小正整数解,就还是原来那个方法:

X%=M;
if (X<0) X+=M;

参考博客

这篇题解是我看了那么多讲得最清楚的一篇了….虽然证明的那个地方笔误了。。。好在对照下代码就看出来了(个鬼,我问了好几个人,想到现在。。。最后发现是笔误。好气啊

这道题实际上给出了解线性同余方程组的一般做法(即,不要求所有的m两两互质)

这种做法的理论依据是扩展欧几里得算法,和中国剩余定理没什么关系…

不过既然都是解线性同余方程组。。。非要把这种做法叫什么ex_crt…我也不是很反对….

 

 

 

poj 1006 Biorhythms (中国剩余定理模板题)

题目链接:

题意:人自出生起就有体力,情感和智力三个生理周期,分别为23,28和33天。一个周期内有一天为峰值,在这一

天,人在对应的方面(体力,情感或智力)表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日

期,分别对应于体力,情感,智力出现峰值的日期。然后再给出一个起始日期,要求从这一天开始,算出最少

再过多少天后三个峰值同时出现。

 

思路:解一个线性同余方程。crt的模板题。

关于crt的讲解:中国剩余定理学习笔记

几年前就A过了,现在重新写题解复习一下。

 

 

poj 2142 The Balance (扩展欧几里得算法)

题目链接

题意:给出a,b,d,分别表示a,b两种刻度的砝码,以及要称量的物体重量为d.现在保证能称量出给定重量的物体,问两种砝码个数的和最小的时候,两种砝码分别有多少。如果有多组解,那么要求weight of(ax + by) 最小。

 

思路:求特解直接扩展欧几里得…

关键是怎么找到绝对值和最小的。。

我就是两个方向跑了下。。。

一开始因为把weight of (ax+by)  (求得还是绝对值最小)理解成了 ax+by最小。。导致WA了半天。。。。sigh….

 

 

poj 2115 C Looooops (扩展欧几里得算法)

题目链接

题意: 问 循环for ( int i = a ; i !=b; i+=c)在% (2^k)的意义下循环了多少次。

思路:

一般的思路是:

列方程…

化成扩展欧几里得算法的形式。。。

根据裴蜀定理判断解是否存在…

然后用对用扩展欧几里得算法求出的X,Y按照题目要求调整。

 

hdu 2669 Romantic (扩展欧几里得模板题)

题目链接

题意:问a*x+b*y=1的一组x>0的解,如果无解输出sorry.

思路:根据裴蜀定理, a*x+b*y=1有解当且gcd(a,b)=1。

然后根据扩展欧几里得算法,我们可以得到一组x,y。需要注意的是,这只是其中一组解。

x,y的通解为:(x+k*gx , y-k*gy ) 其中:gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 

 

 

中国剩余定理(crt)学习笔记

 

前置技能点:

维基百科_裴蜀定理(贝祖等式)

对任何整数a, b和它们的最大公约数d,关于未知数xy线性丢番图方程(称为裴蜀等式):ax+by=m

有整数解时当且仅当md倍数。裴蜀等式有解时必然有无穷多个整数解,每组解xy都称为裴蜀数,可用扩展欧几里得算法求得。

特别地,方程 ax+by=1 有整数解当且仅当整数ab互素。(kk:因为1(m=1)只可能是1(d=1)的倍数,也就是说gcd(a,b)=1,即a,b互质)

 

继续阅读“中国剩余定理(crt)学习笔记”

二次剩余(Cipolla’s algorithm)学习笔记

先放资料。


 

前置技能点:
剩余系

剩余系:设模为m,则根据余数可将所有的整数分成m类,分别记成[0],[1],[2],[m-1]
m个数{0,1,2,m-1}称为一个完全剩余系,
每个数称为相应类的代表元。
当m=10(偶数)时候,则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系
{-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系
{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小
{1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系
简化剩余系:在每个剩余类选取至1个与m互素代表元构成简化剩余系。
当m=10则,{0,1,2,3,4,5,6,7,8,9} 完全剩余系
{1,3,7,9}是简化剩余系(x,10)=1
当m=5则,{0,1,2,3,4}为完全剩余系,
{1,2,3,4}是简化剩余系,因为除去余0(正好是倍数)外,其它都互素。
f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|
=简化剩余系的元素个数

继续阅读“二次剩余(Cipolla’s algorithm)学习笔记”

bestcoder #88 || hdu 5908 Abelian Period(暴力)

题目链接

题意:一段数字串,如果一个数字k满足,将该串分成若干个长度为K的子串,这些子串两两满足每个字符出现的次数一样多,那么称为k是一个阿贝尔周期。现在问所有合法的阿贝尔周期。

思路:

  • 首先我们发现,所有的阿贝尔周期一定是数字串长度(设为n)的因数。
  • 然后我们还发现。。。如果某个因子是阿贝尔周期,那么该因子的整数倍中恰好也是n的因子的也一定是阿贝尔周期,类似筛法。
  • 然后我们还发现。。。最小的阿贝尔周期一定比数字串中的元素个数大。。。

 

2016-10-02-00-07-21-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

然而其实后面两个不管也可以过吧。。。因为有点忘了n的约数个数的上界了。。。。

还是太保守了。。。

不过hack了四发哈哈哈。。。要是大号的话今天就紫了呜呜呜

2016-10-01-21-11-30-%e7%9a%84%e5%b1%8f%e5%b9%95%e6%88%aa%e5%9b%be

 

 

 

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数%1E9+7的答案是多少。

思路:这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数,意义为小于等于n并且与n互质的数的个数。

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.

如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。

考虑两个数a,b的欧拉函数。

一开始考虑也许有什么性质。。。查了下欧拉函数的wiki
欧拉函数_维基百科
欧拉函数是积性函数(但不是完全积性函数。。因此必须phi(ab) =phi(a)*phi(b)成立当且仅当gcd(a,b)==1)

然而这里并不一定满足互质的条件。。。

 

再想一下。。。发现完全没必要由phi(a)和phi(b)得到phi(a*b)

直接把a*b看成一个数就好了。。。。

后面质因子乘积部分只需要把两部分的并在一起就好了。。。

所以根据上面欧拉函数的公式。。。答案分为两部分。。。

一部分是区间中所有数的乘积。。。

一部分是区间中所有数的不相同的素因子的p-1/p形式的乘积。。。

第一部分预处理前缀积即可。。。由于有%运算。。。所以除的时候需要计算逆元。。。

第二部分的做法同spoj_dquery解题报告

也是离线处理,把询问按照区间右端点排序升序排列,然后lst数组记录上次该数出现的位置。。。用bit维护一个从1到某个数的乘积。。。在撤销的时候同样需要逆元。。。

 

还要注意。。。太长的式子一定要分开写。。。。

因为写错括号顺序调了半天orz…