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 为整数，并 …

题目链接 题意： 问 循环for ( int i = a ; i !=b; i+=c)在% （2^k）的意义下循环了多少次。 思路： 一般的思路是： 列方程... 化成扩展欧几里得算法的形式。。。 根据裴蜀定理判断解是否存在... 然后用对用扩展欧几里得算法求出的X,Y按照题目要求调整。 /* *********************************************** Author :111qqz Created Time :Thu 13 Oct 2016 03:57:06 PM CST File Name :code/poj/2115.cpp …

题目链接 题意：两只青蛙初始在数轴的x,y点，单位时间内分别可以向右跳m米和n米，数轴是环型的，长度为L，问两只青蛙能否相遇，以及相遇时跳的次数。 思路：相遇就是同一时间在同一地点。  那么有方程 x+ Cm = y + Cn + k*L 其中C为跳的次数，k为之间差了L的个数（可以理解为被套圈的圈数） 化简得到 C(m-n) + K*L = y-x. 根据裴蜀定理，该方程有解，当且仅当y-x是gcd(m-n,L)的倍数。 然后根据扩展欧几里得算法，需要注意的是其中可能有负数。 如果a是负数， …

题目链接 题意：问ax+by=1的一组x>0的解，如果无解输出sorry. 思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。 然后根据扩展欧几里得算法，我们可以得到一组x,y。需要注意的是，这只是其中一组解。 x,y的通解为：**(x+kgx , y-kgy ） 其中：gx= b/gcd(a,b),gy = a/gcd(a,b),k为任意整数 ** /* *********************************************** Author :111qqz Created Time :Wed 12 Oct 2016 07:30:20 PM CST File Name …

前置技能点： 维基百科_裴蜀定理（贝祖等式） 对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …