Menu Sidebar
Menu

SPOJ

[SPOJ] FACVSPOW – Factorial vs Power

原题:http://www.spoj.com/problems/FACVSPOW/ 题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n 分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code

可是tmd怎么也过不了. 后来想想是二分搜索, 首先, 假设n可以满足, 那么n+1肯定满足. 所以我们可以用二分搜索每次忽略一半. 其次就是怎么计算fact. 翻书啊,翻书 翻到了Stirlings Approximation, 真是简便的公式: . 然后就是low bound就是2*a吧, 但是high bound是啥啊…我数学不好, 真的算不出来. 就靠试数了..反正spoj也没提交限制…

 

[SPOJ] ABCDEF – ABCDEF

原题:http://www.spoj.com/problems/ABCDEF/ 题目大意:计算一个集合S,范围在[-30000,30000], 其中所有的可能的整数abcdef. 满足: (a*b+c)/d-e=f, where d !=0. 问多少种情况 分析: 公式题, 首先是整数取值, 所以就不难.先化简成a*b+c=d(e+f), 然后数一下左边集合中每个在右边的的个数. 注意: 这里是每个元素, 包括重复的. SPOJ真是卡空间, 用map直接TLE, 好好自己写counter吧. d不能是0

Newer Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.