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

题目链接 题意：一个人有n元前，他要交的税是n的最大因子（除n外)，现在这个投机倒把者想把前分成k部分(k为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。 思路：要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想 内容是：任何一个大于２的偶数可以写成两个素数的和。 （虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的２３３３ 那么任何大于２的偶数，答案就是２ 奇数可以分成一个３和一个偶数，答案为３． 不过这可能还不够优，这也是这道题的两个trick所在： 如果该数本身为素数，那么不用分（k取１），答案为１ 如果该数减去２为素数，那么答案为２． /* …

题目链接 题意：求一个楼梯数%m的大小。 思路：指数循环节。 需要注意的是，模数只有最外层是m，每往里一层，模数都变成m=phi(m) 所以可以写个dfs或者先预处理出每一层m存一下。 记得考虑n=1的特殊情况。 /* *********************************************** Author :111qqz Created Time :Wed 26 Oct 2016 07:07:27 PM CST File Name :code/uva/10692.cpp ************************************************ */ #include …

题目链接 题意：定义s(k)为将n分成k个正整数的划分数，给出n，问s(1) + s(2) + ... + s(n-1) + s(n)是多少，结果9+7，其中n<=10^100000。 思路：首先化简要求的式子。 根据隔板法_维基百科 现在有10个球，要放进3个盒子里 ●●●●●●●●●● 隔2个板子，把10个球被隔开成3个部分 ●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、...... 如此类推，10个球放进3个盒子的方法总数为{ n个球放进k个盒子的方法总数为{ 问题等价于求{ 的可行解数， …

题意：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 ≡ …

资料先行： 指数循环节证明 指数循环节2 对指数循环节的一些理解 挂了一点题目，写完来写总结。 vjudge_不会指数循环节的111qqz 写完了。 首先要注意的是： 首先我们知道指数循环节公式，也就是所谓的降幂公式为：**a^x = a^(x mod phi(c)+phi(c)) (mod c) x=phi(c)，（ps:后面的限制条件，在x）** 括号里的话是错误的。当x<phi(c)时，该式子是错误的。 之前一直没出问题是因为数据水。 参考题目：hdu3221解题报告

题目链接 题意：给出k个方程，形式为 x==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=m1k1+r1………………………………………………………………() X=m2k2+r2 那么 m1k1+r1=m2k2+r2 整理， …

题目链接： **题意：**人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一 天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日 期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少 再过多少天后三个峰值同时出现。 思路：解一个线性同余方程。crt的模板题。 关于crt的讲解：中国剩余定理学习笔记 几年前就A过了，现在重新写题解复习一下。 /* *********************************************** Author :111qqz Created Time …

题目链接 题意：给出a,b,d，分别表示a,b两种刻度的砝码，以及要称量的物体重量为d.现在保证能称量出给定重量的物体，问两种砝码个数的和最小的时候，两种砝码分别有多少。如果有多组解，那么要求weight of(ax + by) 最小。 思路：求特解直接扩展欧几里得... 关键是怎么找到绝对值和最小的。。 我就是两个方向跑了下。。。 一开始因为把weight of (ax+by) （求得还是绝对值最小）理解成了 ax+by最小。。导致WA了半天。。。。sigh.... /* *********************************************** Author :111qqz Created Time :Thu …

题目链接 题意： 问 循环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 …