1.2 简单的数学计算
以上那样利用循环重复将部分数据简单地累加，可以解决很多计数问题。然而，如果计数问题可以通过数学计算直接得出结果，往往可以大大改善算法的时间效率，请看下列问题。
问题1-5 小小度刷礼品
图片 7
问题描述
一年一度的百度之星大赛又开始了，这次参赛人数创下了吉尼斯世界纪录。于是，百度之星决定奖励一部分人：所有资格赛提交ID以x结尾的参赛选手将得到精美礼品一份。
小小度同学非常想得到这份礼品，于是他就连续提交了很多次，提交的ID从a连续到b。他想知道能得到多少份礼品，你能帮帮他吗？
输入
第一行一个正整数T表示测试案例数。
接下来T行，每行3个不含多余前置零的整数x，a，b（0leqslantxleqslant1018，1leqslantaleqslantbleqslant1018）。
输出
T行。每行为对应的数据下，小小度得到的礼品数。
输入样例
2
88888 88888 88888
36 237 893
输出样例
1
6
解题思路
（1）数据的输入与输出
题面中告诉我们，输入文件的第一个数据指出了所含的测试案例数T，每个案例的输入数据仅占一行，其中包含了3个分别表示ID尾数x、ID取值下界a和上界b的整数。计算所得结果为a～b内能够得到礼物的ID（尾数为x）个数，作为一行输出到文件中。表示成伪代码如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据x, a, b
6 result← GIFT(x, a, b)
7 将result作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用过程GIFT (x, a, b)计算能够得到的礼物数是解决一个案例的关键。
（2）处理一个案例的算法过程
对一个测试案例x, a, b而言，很容易想到用列举法穷尽a～b所有的整数，检测每一个的尾数是否与x相等。跟踪相等的个数：
GIFT (x, a, b)
1 t← x的10进制位数
2 m←10t
3 count ←0
4 for i ←a to b
5 do if i Mod m=x
6 then count ←count+1
7 return count
算法1-5 对一个测试案例数据x, a, b，累加计算获得礼品数的算法过程
算法1-5中的第1、2行计算m=10t，其中t为x的10进制位数，可以用如下操作实现：
1 m←1
2 while m<x
3 do m←m*10
显然耗时为log10x，若a～b之间有n个数，则上述算法中第3～6行代码的运行时间是Θ(n)，于是算法1-5的运行时间为Θ(log10x)+ Θ(n)。借助数学计算，我们可以把解决这个问题的算法时间缩小为Θ(log10x)。设x的10进制位数为t，令m为10t。例如，若x=36，a=237，b=893，则t=2，m=100。设ar =a Mod m，aq=a/m 。即ar为a除以m的余数，aq为a除以m的商。相仿地，设br=b Mod m，bq=b/m。对于x=36，a=237，b=893，有ar =37，aq=2，br=93，bq=8。由于ar =37>36=x，所以a(=237)之后最小的位数为x(=36)的数应为336。而由于br=93>36=x，故在b=893之前最大的尾数为36的数为836。因此，介于a，b之间尾数为x的数为336，436，536，636，736，836，一共有bq− (aq+1)+1＝6个。
上例说明，对于x, a, b，若aleqslantxleqslantb，计算出ar =a Mod m，aq=a/m ，br=b Mod m，bq=b/m后，检测ar是否大于x。若是，则aq增1。相仿地，检测br是否小于x，若是，则bq减1。bq−aq+1即为所求。写成伪代码过程如下。
GET-GIFT(x, a, b)
1 t← x的10进制位数
2 m←10t
3 ar ←a Mod m，aq←a/m
4 br ←b Mod m，bq←b/m
5 if ar>x
6 then aq←aq+1
7 if br<x
8 then bq←bq-1
9 return bq-aq+1
算法1-6 对一个测试案例数据x, a, b，直接计算获得礼品数的算法过程
算法1-6中的第1～2行与算法1-5中的一样，耗时Θ(log10x)。而算法其余部分耗时为Θ(1)。于是，算法1-6的运行时间为Θ(log10x)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Get Gift中，读者可打开文件getgift.cpp研读，并试运行之。
问题描述
农夫John养了一群牛妞。有些牛妞很任性，时常离家出走。一天，John 得知了他的一头在外流浪的牛妞出后想立刻去把她领回家。John从数轴上的点N (0leqslantNleqslant100 000)处出发，牛妞出没于同一数轴上点K (0leqslantKleqslant100 000)处。John有两种移动方式：走路或远距飞跃。
走路：John在一分钟内可从点X走到点X-1或点X+1处。
远距飞跃：John可以在一分钟内从任意点X处飞跃到点2X处。
假定牛妞对自身的危险一无所知，一直在原地溜达，John最少要花多少时间才能够抓到她？
输入
输入文件的第一行仅含一个表示测试案例个数的整数T。其后跟着T行数据，每行数据描述一个测试案例，包括两个用空格隔开的整数：N和K。
输出
每个案例只有一行输出：John抓到牛妞的最少时间（分钟）。
输入样例
2
5 17
3 21
输出样例
4
6
解题思路
（1）数据的输入与输出
根据题面中对输入、输出数据的格式描述，我们可以将处理所有案例的过程表示如下。
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5 do 从inputdata中读取案例数据N, K
6 result←CATCH-THAT-COW(N, K)
7 将result作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata
其中，第6行调用过程CATCH-THAT-COW(N, K)计算John从N出发抓到位于K的牛妞要用的最短时间是解决一个案例的关键。
（2）处理一个案例的算法过程
John要想最快地从点N到达点K处，就要充分利用他的飞跃能力。需要注意的是，John步行时可来回走，而飞越只能是单向的。所以，当NgeqslantK时，John 只能从N步行到K（见图1-2（a））。此时，需要走N-K分钟。
考虑NK（见图1-2（b））。最理想的情况是N2q=K， 此时q即为所求。否则John有两个可能的走法：
① 从N飞跃q 次到达N2q，再往前走K−N2q分钟到达K，即用时为q+K−N2q分钟。
② 从N飞跃q+1次到达N2q+1，再往回走N2q+1−K分钟到达K，即用时为q+1+ N2q+1−K分钟。
取两者较小者可能是最优解。然而这并不全面，因为还有更加微妙的情况会出现。以题面的输入样例N=5，K=17为例。2×5<17，且22×5>17。按第①种方案，需用1+7=8分钟，而用第（2）种方案需用2+3=5分钟。但是，如果John先从N=5往回走1分钟，来到4(=22)处，然后从22处飞跃2次来到24(=16)处，再从24向前走1分钟就可到达K=17，这样所用的时间为4分钟，更短。
形式化地说，设不超过N的2的幂之最大者为2t，而不超过K的2的幂之最大者为2p。于是必有2tleqslantN<2t+1及2pleqslantK<2p+1（见图1（c））。此时，John 可以有4种不同的走法：
① 从N步行到2t，从2t飞跃到2p，再从2p走到K。用时：(N−2t)+(p−t)+(K−2p)。
② 从N步行到2t，从2t飞跃到2p+1，再从2p+1走到K。用时：(N−2t)+(p−t+1)+(2p+1−K)。
③ 从N步行到2t+1，从2t+1飞跃到2p，再从2p走到K。用时：(2t+1−N)+(p−t+1)+(K−2p)。
④ 从N步行到2t+1，从2t+1飞跃到2p+1，再从2p+1走到K。用时：(2t+1−N)+(p−t)+(2p+1− K)。
所以，若令a=q+K−2qN，b=q+1+2q+1N−K，c=(N−2t)+(p−t)+(K−2p)，d=(N−2t)+(p−t+1)+(2p+1−K)，e=(2t+1−N)+(p−t+1)+(K−2p)，f=(2t+1−N)+(p−t)+(2p+1−K)，则min{a, b, c, d, e, f}即为所求。上述算法可写成如下的伪代码。
CATCH-THAT-COW(N, K)
1 if N\geqslantK
2 then return N-K
3 p←max{i|2i\leqslantK}, q←max{i|2iN\leqslantK}, t←max{i|2i\leqslantN}
4 if N2q=K
5 then return q
6 a← q+K-N2q , b← q+1+ N2q+1-K, c←(N-2t)+(p-t)+(K-2p)
7 d←(N-2t)+(p-t+1)+(2p+1-K), e←(2t+1-N)+(p-t+1)+(K-2p), f ←(2t+1-N)+(p-t)+(2p+1-K)
8 return min{a, b, c, d, e, f}
算法1-7 计算农夫John 从N到K最少时间的算法过程
算法1-7中，第3行计算不超过某整数x的最大的2的整幂指数，可以通过如下过程进行。
CALCULATE(x)
1 p←1, t←0
2 while p<x
3 do p←p*2
4 t←t+1
5 if p>x
6 then t←t-1
7 return t and 2t
算法1-8 计算不超过最大的2的整幂指数的整数x的算法过程
由于tleqslantlgx，而第2～4行的while循环每次重复t（从0开始）都会增加1，所以该循环至多重复lgx次。于是算法1-8的运行时间为Θ(lgx)。算法1-7的第3行调用三次CALCULATE过程就可完成指数p，2p，q，N2q，t，2t的计算，而算法的其他部分均在常数时间内完成，所以算法1-7的运行时间为O(lgK)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/Catch The Cow中，读者可打开文件Catch The Cow.cpp研读，并试运行之。
有些问题需要综合地使用数学计算和累加和方法加以解决。
描述
你是个暴脾气，最讨厌等待。你打算去新奥尔良拜访一位朋友。来到公交站你才发现这里的调度表是世界上最糟糕的。这个车站并没有列出各路公交车班车到达与出发的时间表，只列出各相邻班车的发车间隔时长。暴躁的你从包中抓出平板电脑，试图写一段程序以计算最近来到的班车还需要等待多久。嘿，看来你只能这样了，不是吗？
输入
本问题的输入包含不超过100个测试案例。每个案例的输入数据格式如下。
一个测试案例的数据包括四个部分：
开头行——只有一行，“START N”，其中的N表示公交车路数（1leqslantNleqslant20）。
路线发车间隔区间行——共有N行。每行由M（1leqslantMleqslant10）个发车间隔时长组成，这些数据表示这一路线的各班车上一班发车起到本班车出发时刻的间隔时间长度。每个间隔时长是一个介于1～1000之间的整数。
到达时间——仅一行。该行数据表示你到达车站开始等待的时间。这个数据表示的是从当天车站开始运行到你来到车站的时间单位数（所有的线路的车都是从时间0开始运行的）。这是一个非负整数（若为0，意味着班车在你到站时起步）。
结束行——单一的一行，“END”。
最后一个测试案例后有一行“ENDOFINPUT”，作为输入结束标志。
输出
对每一个测试案例，恰有一行输出。这一行仅包含一个表示你在下一趟班车到来之前需要等待的时间单位数。我们希望你等来的这班车是去往新奥尔良的！
注意
每班公交连续不断地循环运行于它的线路上。
若乘客在班车离开时刻到达，他/她将搭上这班车。
输入样例
START 3
100 200 300
400 500 600
700 800 900
1000
END
START 3
100 200 300 4 3 2 4 2 22
800
10 1000
32767
END
ENDOFINPUT
输出样例
200
20
解题思路
（1）数据的输入与输出
按题面对输入文件的格式描述，输入包含多个测试案例，每个案例的第一行包含两个部分：开头标志“START”和表示本案例中公交车的路数N。案例数据接下来的N行数据表示每一路车各相邻班车的发车间隔。接着一行仅含一个表示乘客到达时间的整数。最后一行是案例结束标志“END”。例如，输入样例中第一个案例的第1行数据START 3表示该案例有3路公交车。后面3行数据表示各路公交的各班车的发车间隔，例如第1行的数据100 200 300表示1路车的第1、2班车的发车间隔为100，第2、3班车的发车间隔为200，第3、1班车的发车间隔为300。以此类推。最后一行数据1000表示乘客到来的时刻。
文件的结束标志是一行“ENDOFINPUT”。
依次读取每个案例的数据，将发车间隔数据组织成一个表durations，到达时间记为arrival，对案例数据进行处理，计算得到乘客最小等待时间，并将结果作为一行写入输出文件。描述成伪代码如下：
1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取一行到s
4 while s≠"ENDOFINPUT"
5 do 略过s中的"START"，并读取N
6 创建数组durations[1..N]
7 for i←1 to N
8 do从inputdata中读取一行到s
9 将s中的每一个整数数据添加到durations[i]中
10 从inputdata中读取arrival
11 result←WORLD-WORST-BUS-SCHEDULE(durations, arrival)
12 将result作为一行写入outputdata
13 在inputdata中略过一行"END"
14 从inputdata中读取一行到s
15 关闭inputdata
16 关闭outpudata
其中，第11行调用过程WORLD-WORST-BUS-SCHEDULE(durations, arrival)计算乘客最小的等车时间，是解决一个案例的关键。
（2）处理一个案例的算法过程
对一个案例而言，将各路车的出发间隔时长记录在一组数组durations中，durationsi表示第i路车第j次发车距第j-1次发车的时间间隔。Ti=sumnolimits_{j=1}^{{{m}_{i}}}{durationsi}表示第i路各班车运行一个循环所用的时间（i=1, 2,…,n）。若设本案例中乘客的到达时间为arrival，则Ri=arrival MOD Ti表示乘客来到车站时，第i路车运行完若干个循环周期后处于最新运行周期内的时间。例如，输入样例中的案例1中1路车3班车的一个运行周期T1为100+200+ 300=600，乘客到达时间arrival=1000，R1=arrival MOD T1=1000 MOD 600≡400。这意味着1路车的3班车已经运行了一个循环后400时乘客到达车站。于是，乘客需要等待的应该是当前周期内从开始到最近发车时间超过400的那班车。等待的时间自然就是从第一个使得差sumnolimits_{j=1}^{{{m}_{i}}}{durationsi}−Rigeqslant0（1leqslantkleqslantmi）的值。本例中此值为(100+200+300) −400 = 600 – 400=200。所有n路的等待时间中的最小值即为所求。以上算法思想写成伪代码过程如下。
WORLD-WORST-BUS-SCHEDULE(durations, arrival)
1 n←length[durations]
2 for i←1 to n
3 do mi←length[durations[i]]
4 Ti←durations[i][j]
5 Ri← arrival MOD Ti
6 k←1
7 while durations[i][j]-Ri <0
8 do k←k+1
9 time[i] ←durations[i][j]-Ri
10 return min(time)
算法1-9 计算乘客最小等待时间的算法过程
设案例中有n路公交，其中班次最多的班数为m。算法的运行时间取决于第2～9行的两层嵌套循环重复次数。外层for循环重复n次，里层的第4行实际上也是一个循环（计算累加和），重复次数最多为m。同样，第7～8行的while循环也至多重复m次。这两个内层的循环是并列的，所以运行时间为O(nm)。
解决本问题的算法的C++实现代码存储于文件夹laboratory/ World's Worst Bus Schedule中，读者可打开文件World's Worst Bus Schedule.cpp研读，并试运行之。