Jian's Note

It's better to burn out than fade away!

Dreamoon and Stairs

题目链接 Dreamoon wants to climb up a stair of n steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer m. What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition? Input The single line contains two space separated integers n, m (0 < n ≤ 10000, 1 < m ≤ 10). Output Print a single integer — the minimal number of moves being a multiple of m. If there is no way he can climb satisfying condition print - 1 instead. Examples input 10 2 output 6 input 3 5 output -1 Note For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}. For the second sample, there are only three

The equation-SGU106(扩展欧几里得)

题意: 给出 a,b,c,x1,x2,y1,y2,求满足 ax+by+c=0,且 x∈[x1,x2],y∈[y1,y2] 的整数解个数。 分析: 对于解二元一次不定方程,容易想到利用扩展欧几里得求出一组可行解后找到通解,下面来介绍一下欧几里得以及扩展欧几里得。 欧几里得: 又名辗转相除法,是用来计算两个数的最大公约数

Leading and Trailing-lightoj1282(快速幂+对数运算)

题目链接

题目大意:

给定两个数 n,k 求 n^k 的前三位和最后三位。

分析

求后三位的话:直接快速幂,对 1000 取模就好了。
求前三位,对于给定的一个数 n, 它可以写成 n=10^a, 其中这个 a 为浮点数,则t=n^k=(10^a)^k=10^a*k=(10^x)*(10^y);其中 x,y 分别是a*k的整数部分和小数部分,对于 t=n^k 这个数,它的位数由 (10^x) 决定,它的位数上的值则有 (10^y) 决定,因此我们要求 t 的前三位,只需要将 10^y 求出,在乘以 100,就得到了它的前三位。
分析完,我们再整体看,设 n^k=10^z; 那么z=k*log10(n)
fmod(z,1)可以求出 x 的小数部分。

欧拉函数

欧拉函数是求小于 x 并且和 x互质 的数的个数

通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中 p1, p2……pn 为 x 的所有质因数,x 是不为 0 的整数
φ(1)=1(唯一和 1 互质的数就是 1 本身)【注意:每种质因数只一个。比如 12=223】

定理:

  1. 若 n 是素数 p 的 k 次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了 p 的倍数外,其他数都跟 n 互质
  2. 欧拉函数是积性函数——若 m,n 互质,φ(mn)=φ(m)φ(n)

特殊性质:

  1. 当 n 为奇数时,φ(2n)=φ(n)
  2. p 是素数,φ(p) = p - 1,φ(p) 称为 p 的欧拉值
  3. 若 a 为素数,b mod a=0,φ(a*b)=φ(b)*a

Heavy Transportation-poj1797(dijkstra 或最大生成树)

题目链接](http://poj.org/problem?id=1797)
大意:
要从城市 1 到城市 N 运送货物,有 M 条道路,每条道路都有它的最大载重量,问从城市 1 到城市 N 运送最多的重量是多少。
其实题意很简单,就是找一条 1–>N 的路径,在不超过每条路径的最大载重量的情况下,使得运送的货物最多。一条路径上的最大载重量为这个路径上权值最小的边;

Til the Cows Come Home-poj2387(dijkstra 判断重边)

题目链接 题目大意: 说的是,一只奶牛位于 N 号节点,输入 N 个节点和 T 对双向的边,求出由 N 到 1 的最短的距离,其实就是问的单源最短路问题。 两个点可能有多条路,选择最短的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int INF=99999999; //设为无穷

最短路入门

Dijkstra 算法 1. 定义概览 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注
0%