0

UVa - 11400 - Lighting System Design(线性动态规划)

• liqin2011 发布于
• 946 收藏

题目意思是 小灯泡(低电压)可以换成大灯泡，但是需求的数目不变，一种灯泡只买一个电源就可以。 举个例子 灯泡a和b。 a 电压 1 电源 50元 单价 5 需要 5 b 电压 2 电源 20元 单价 6 需要 4 买小灯泡的话，需要50+5*5=75 加上大灯泡的20+4*6+75 = 119元 如果把小灯泡换成大灯泡，虽然单价大灯泡贵，但是就不用买小灯泡的电源，就需要20+（5+4）*6 = ...

0

数论模板总结

• liqin2011 发布于
• 1404 收藏

1.离散对数 ax≡b(modp)那么x≡loga（b)(modp) 那么现在我们就来求解这个x. 朴素baby step giant step要求p必须为质数. 整体的复杂度为O(n√)). //Hash + 扩展欧几里得 +拆分思想 /* 求解模方程a^x=b(mod n)，n为素数。 模板题。 时间复杂度O(sqrt(n)*logn) ...