快速求约数(divisor)

一个通常情况足够快,且好写的求约数算法

GDB 调试极简入门

GDB 是 GNU 提供的流行Debug 工具,GDB 可以对任何可执行文件进行Debug

使用GDB 启动程序

最简单的方法

gdb ./a.out

如何需要使用命令行参数,则需要使用 --args 参数(下面 someargs 和 arg1 等都只是例子)

gdb –args ./a.out someargs –arg1 value1 –args2 value2

进入GDB后使用 r 开始执行程序
当程序运行遇到关键错误时,GDB会捕获错误并开始调试

当然,最重要的一点,gdb 使用 quit 命令或者 Ctrl + D 退出

使用 Core Dump 调试程序

Linux 支持在程序异常退出时使用 CoreDump 将现场内存保存在磁盘上(文件名默认为core). GDB 可以利用CoreDump文件恢复现场调试。

如果想使用CoreDump,首先要用ulimt 打开 CoreDump 功能

ulimit -c unlimited

这样程序异常退出时才会保存 core 文件。调试时使用

gdb ./a.out core

来启动调试

编译,加入符号信息

gdb 如果不能在可执行文件中找到符号(symbol)信息,调试时功能会受到极大限制,不能方便的使用断点, 不能查看代码,不能定位到崩溃的具体文件和行数。如果想要使用 GDB 调试,一般需要在编译时加上 -g 参数,加入符号信息。

gdb a.cpp -g

如果调试时发现有些变量不能输出,可能是 编译优化级别太高导致。仅在有必要的情况下,可以加入-O0 (注意是大写英文字母O 和阿拉伯数字0)选项

g++ a.cpp -g -O0

常用指令

当触发断点,或者异常中断时,GDB会切换到相应的栈帧 (frame) 等待用户调试

常用的调试指令有

  • bt (backtrace) 打印当前的调用栈
  • p (print) 打印变量内容
  • f (frame) 切换栈帧
  • l (list) 打印当前代码
  • r (run) 从头开始执行
  • c (continue) 继续执行
  • b (breakpoint) 插入断点
  • d (delete) 删除断点

用法在下面介绍

演示

下面给一个含有错误样例代码,演示 GDB 常用的调试命令

g++ debug.cpp -g -O0
gdb ./a.out

显然这段代码会产生除0错误, 先执行(输入r)gdb 输出如下

我们能看到很多信息, 比如错误出现在 debug.cpp 文件的第3行,这行的代码是 return x / y;, 出现的错误是算数错误(Arithmetic exception)

现在可以使用××打印变量××(p 命令)功能,看看 x 和 y 到底是什么

我们知道了,错误是因为 y = 0,出现了除 0 错误

那么为什么会执行这段代码呢?可以使用 list 命令查看附近的代码. 需要指出的是,list 默认向下浏览代码,你可以使用l - 向上浏览代码

到这里我们知道了,y 是 0 的原因 divide 函数的输入参数 y 是 0,那么是谁调用了这个函数呢?我们可以使用 查看调用栈 功能 (bt命令)

我们可以看出,是debug.cpp 的第 6 行 main 函数调用了 divide 函数,还能看到divide 函数的实参是 x = 10, y = 0.
此时我们应当使用切换栈帧 (frame命令) 回到 main 函数查看调用 divide 的代码. #1 代表main 函数的栈帧编号为 1

我们通过切换栈帧和打印代码看到,传给 divide 函数的 y 参数是 循环变量 i. 我们可以打印此时 i 的值

print 指令不仅可以查看变量的值,还能进行简单的运算,例如对vector的元素的访问,可以直接 p vec[10] 这样操作。

最后我们尝试下断点 (breakpoint). 只要gdb等待你的输入,你就可以添加断点,比如我们给 main 函数的 第6行添加断点并重新运行

GDB 的确帮我们中断了程序并进入调试,此时我们可以继续(continue)

断点不是一次性的,再次执行代码会再次触发断点。此时我们可以删除断点(d),需要指出断点编号

最后,退出GDB (quit)

解决Driver/library version mismatch

服务器更新nvidia driver 版本之后,经常会出现

这个问题出现的原因是kernel mod 的 Nvidia driver 的版本没有更新,一般情况下,重启机器就能够解决,如果因为某些原因不能够重启的话,也有办法reload kernel mod。

简单来看,就两步

  1. unload nvidia kernel mod
  2. reload nvidia kernel mod

执行起来就是

  1. sudo rmmod nvidia
  2. sudo nvidia-smi

nvidia-smi 发现没有 kernel mod 会将其自动装载。

但是事情远远不是这么简单,一般情况下都会遇到卸载失败。

这时,就要一点一点的卸载整个驱动了,首先要知道现在kernel mod 的依赖情况,首先我们从错误信息中知道,nvidia_modeset nvidia_uvm 这两个 mod 依赖于 nvidia, 所以要先卸载他们

可以看到 nvidia 被使用了152词,我们可以先卸载 nvidia_uvm 和 nvidia_modeset

先查看下有哪些进程使用了 nvidia*

这些进程有个了解,如果一会卸载失败,记得关闭相关进程。

卸载

再 lsof 一遍,如果 nvidia 的使用 Used by 还没有降到 0,kill 相关进程

最后

收工

CheckAC 在Chrome WebStore 上架

2013年暑假集训,我们(@yangz @alwa)发现了一个小众的需求,即在OJ上做题的时候不能确定一道题自己有没有过掉,尤其是在查看别人的提交记录的时候。

下载地址:CheckAC

Github(欢迎提交意见,代码更好):CheckAC

还有,不知道为什么,我们的集训队一直比较关心一个人的过题数量,于是乎我们都在乎了。

(说来惭愧,暑假之后几乎没怎么搞算法,全都是搞应用了,最近虽然考试多,还是要多刷刷题了,太少了看不过去)

于是,我们就决定开发一款Chrome 的扩展程序(插件),能辅助我们在OJ上做题,想法很好,说干就干。

开发速度简直快的惊人(凭记忆):

2013-7-19 14:00 ~ 2013-7-21  2:40 :

36小时速成0.1版,可惜当时还不会用Github ,没有记录下开发过程

  • 当天自学了如何制作插件
  • 当天晚上搞出了可以在POJ网站上抓取过题数量和通过题目列表的正则表达式
  • 学习了一个东西叫XMLHttpRequest ,知道了这东西能在插件里异步访问Web,后来知道了一个东西叫Ajax
  • 学习了一个叫localStorge的本地存储方法作为插件的存储
  • Chrome 插件有个东西叫ContentScript,能在目标网页中运行,能完成打钩的功能
  • Chrome 插件有个BackGroundPage 通过它我才能读取插件能访问的localStorge 并和ContentScript通信,来告诉ContentScript 那些题目我已经AC
  • 用Photoshop 画了个LOGO
  • 21日凌晨抄袭了”印象笔记剪藏”的CSS样式,然后完成了0.1版

不过这个东西的功能仅限于抓AC列表,点插件输入个POJ题号能用绿色和红色表示你题目有没有AC,发下21日凌晨怀着激动的心情在集训队内部论坛发布时的截图:

CheckAC Alpha 屏幕截图

之后的几天:

  • 听说有个东西叫BootStrap 是个前端框架,用上之后果然非常好使,用它写了Setting 和 popup页面
  • 听说有个东西叫Jquery,是个JS库,用上之后果然非常好使
  • 搞定了ZOJ 的题目抓取功能
  • 学了一个东西叫JSON,能序列化对象,终于不用我人工定义localStorge中字符串的格式了
  • ACM-ICPC信息站找了个近期比赛的JSON源,在此表示感谢

现在,CheckAC 已经有了关注他人,ToDoList 等功能。欢迎大家使用。

为什么现在才上架呢?因为Google WebStore开发者账户要用$5验证,要有信用卡,而且不能是中国大陆的。于是鼓动我父亲给我办了张卡,拿到卡之后非常顺利,2小时就完成了从开发者账户验证到上架的过程,在此也给想在ChromeWebStore上架的朋友说一下我的操作。

  1. 招商银行美国运通(AmericaExpress)双币信用卡
  2. Goagent+Chrome隐身模式登陆Google账号
  3. 填写的是香港地址
  4. 中国正常手机号码

迁移至新域名(comzyh.com)啦

今天下午tk域名解析莫名其妙不正常,感觉tk这个小岛国还是有点不靠谱,于是乎迁移至com域名.

目前301重定向什么的都弄好了,就等Google收录了.用以前的tk域名还能够继续访问,会自动跳转过去的.

正好也试试Word2013直接用Xmlrpc发布文章的功能.

感谢大家支持J

等比数列求和的二分法

常见问题:给定整数M,等比数列\(\{{a_n}\}\),求其前n项和对M的模

朴素的想法,我们可以用等比数列求和公式\(S_n=\frac {a_1(1-q^n)}{1-q}\)求得和再模除M,但是计算过程中取模导致分母下面的1-q不能直接除,要求1-q的乘法逆元;

这里介绍另一种思路,就是使用二分的思想,很像矩阵快速幂
首先,我们先讨论一个简单的问题:
求\(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8\)的和
提取公因式,我们能把原式变为
\((a^1+a^2+a^3+a^4)(1+a^4)\)
进一步变换为\((a^1+a^2)(1+a^2)(1+a^4)\)
\(=a(a+a^1)(1+a^2)(1+a^4)\)
我们把这种等比数列前\(2^k\)项和记为\(S(k)\)有递推式\(S(k)=S(k-1)(1+a^{2^{k-1}})\)
这是二分法的关键,也就是说我们能在log(n)的时间内求出等比数列前\(2^k\)项的和

当我们要求的不是前2的整数次幂的时候,我们将n分解为2的整次幂的和:
比如求前等比数列11项的和,我们将11(二进制表示:1011)分解为1+2+8(二进制表示1+10+1000)
前11项的和可以表示为:
\((a^1)+(a^2+a^3)+(a^4+a^5+a^6+a^7+a^8+a^9+a^{10}+a^{11})\)
可进一步表示为
\(a^0(a^1)+a^1(a^1+a^2)+a^3(a^1+a^2+a^3+a^4+a^5+a^6+a^7+a^8)\)
即:\(a^0S(0)+a^1S(1)+a^3S(3)\)
Well done!我们又把原式分解成了多个\(a^xS(y)\)的和
Continue reading

选取第K大数的快速选择算法和注意事项

快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.

其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.

  1. 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
  2. 判断第k大的数是在小的部分还是大的部分
  3. 递归,直到区间足够小,返回结果

Continue reading

域名删除记录

据监测 ,北京时间2011-6-3 日17时左右,我的域名被注销,鬼知道为什么
为防止域名注册机构再来抓住我神马把柄,本文不用中文
2010-6-8 又注销一次,并且禁止注册。经过我邮件咨询,又恢复一次,客服态度还好,没有纠缠