Dreamoon and WiFi(组合数学)
The equation-SGU106(扩展欧几里得)
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 的小数部分。
Codeforces Round 502(Div.1 + Div.2)
A. The Rank
题目大意:
给出 n 个学生的成绩,Thomas Smith 的成绩是第一行,然后要按总成绩进行排序,总分相同的按编号从小到大排;
开始看还以为要写 sort 的 cmp 函数进行多条件排序,敲完才发现其实只要按总分就可以了,因为托马斯的 id 是一,必然会排在前面。
欧拉函数
欧拉函数是求小于 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】
定理:
- 若 n 是素数 p 的 k 次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了 p 的倍数外,其他数都跟 n 互质
- 欧拉函数是积性函数——若 m,n 互质,φ(mn)=φ(m)φ(n)
特殊性质:
- 当 n 为奇数时,φ(2n)=φ(n)
- p 是素数,φ(p) = p - 1,φ(p) 称为 p 的欧拉值
- 若 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 的路径,在不超过每条路径的最大载重量的情况下,使得运送的货物最多。一条路径上的最大载重量为这个路径上权值最小的边;
hexo 博客自定义 console log
看到知乎,百度的页面 F12 检查后都会有一些有趣的招聘信息。于是乎我也想给我的博客加一个。
我主要用到的工具:
- console.log()
- Notepad++
- 在线图片转文字工具