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为大于等于１的任意值）每部分不能为１，分别交税，问最少交多少税。

题目链接

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

思路：指数循环节。

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

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

题目链接

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

题意：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))

资料先行：

指数循环节证明

指数循环节2

对指数循环节的一些理解

挂了一点题目，写完来写总结。

vjudge_不会指数循环节的111qqz

写完了。

首先要注意的是：

首先我们知道指数循环节公式，也就是所谓的降幂公式为：**a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c)，（ps:后面的限制条件，在x）**

括号里的话是错误的。当x<phi(c)时，该式子是错误的。

题目链接

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

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

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

题目链接：

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

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

题目链接

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

题目链接

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

思路：

一般的思路是：

列方程…

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

题目链接

题意：问ax+by=1的一组x>0的解，如果无解输出sorry.

思路：根据裴蜀定理， ax+by=1有解当且gcd(a,b)=1。

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

前置技能点：

维基百科_裴蜀定理（贝祖等式）

对任何[整数](https://zh.wikipedia.org/wiki/) ，  和它们的[最大公约 …

先放资料。

前置技能点：

剩余系

剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**

这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系，

阅读更多

题目链接

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

题目链接

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

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

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

1053: [HAOI2007]反素数ant

Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2750  Solved: 1559 [Submit][Status][Discuss]

Description

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x

题目链接

题意：求约数个数恰好为n个的最小的x

思路：这道题是作为反素数的例题出现在acdreamer的博客里的。

但是实际上，这道题应该和反素数没有关系。

如果题目问的是最小的约数个数大于等于n的x，那么答案一定是反素数…打表就行了。。。

题目链接

题意：求区间[a,b]中约数最多的那个数，如果有多个，输出最小的。

思路：看起来好像和反素数没什么关系…只是打个约数个数的表…

acdreamer的博客

wiki上的反素数是什么鬼orz…完全不是一个东西吧。。。。

反素数直观得理解。。。就是一个约数特别多的数。。。因为素数的约数最少。。。所以约数多的数就叫反素数（？随便口胡的…

题目链接

题意：给出n个数，m个查询，每组查询一个区间[l,r]，问[l,r]中会被吃掉多少个（区间[l,r]中的数只有当其是其他所有数的因数时才不会被吃掉,顺便问一句。。a divide b 是 a除b,也就是b除以a,b/a的意思嘛23333）