2.8　数学概念与方法

本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第10章。

习题10-1　砌砖（Add Bricks in the Wall，UVa11040）

对45块石头按照如图2.60所示的方式排列，每块石头上有一个整数。

除了最后一行外，每个石头上的整数等于支撑它的两个石头上的整数之和。目前只有奇数行的左数奇数个位置上的数已知，你的任务是求出其余所有整数。输入保证有唯一解。

【分析】

把所有石头看作一个二维数组B［9］［9］。从上到下依次是0～8行。则对于i＝0，2，4，6，8这样的偶数行，已知数字就是B［0］［0］、B［2］［0］、B［2］［4］这样的偶数列。我们观察第8行的左数第1个空格，假设里面是x，则其上方的两个石头分别为2＋x、x＋1，继续往上就有2＋x＋x＋1＝3，这样就可以解出x。

推广开来，对于奇数列来说，B_i，j满足：

所以有：

从下到上把所有的偶数行奇数列的数字计算出来之后，奇数行的数字按照题目所述规则也自然可以计算出来。

习题10-2　勤劳的蜜蜂（Bee Breeding, ACM/ICPC World Finals 1999, UVa808）

如图2.61所示，输入两个格子的编号a和b（a,b≤10000），求最短距离。例如，19和30的距离为5（一条最短路是19-7-6-5-15-30）。

【分析】

在一个平面上任选两个向量，就可以建立一个坐标体系（本题中已经不是笛卡尔坐标系）表示平面上所有的点。如图2.62所示，使用块1→7的方向作为正X轴，1→6的方向作为正Y轴。XY轴把平面分成4个象限，同时用6个方向向量表示6个方向：{-1,0}, {-1,1}, {0,1}, {1,0}, {1,-1}, {0,-1}。

首先确定块1和2的坐标(0,0)和(1,-1)，观察后可以得出，点的坐标遵循如下规律。

第1圈：

2→3, 3→4, 4→5, 5→6,分别使用向量{-1,0}, {-1,1}, {0,1}, {1,0},每次生成1个点。

6→8，使用向量{1,-1}，生成2个点。

8→9，使用向量{0,-1}，生成1个点。

第2圈：

9→11, 11→13, 13→15, 15→17,分别使用向量{-1,0}, {-1,1}, {0,1}, {1,0},每次生成2个点。

17→20，使用向量{1,-1}，生成3个点。

20→22，使用向量{0,-1}，生成2个点。

……

依次类推，就可以生成所有点的坐标。对于任意的两个点(x₁, y₁), (x₂, y₂)，记x=x₁–x₂, y=y₁–y₂，则这个两点之间的距离就是原点到(x,y)的距离。

观察之后不难发现：第1、3象限的点(x, y)到原点的距离为|x|+|y|；第2、4象限的点(x, y)到原点的距离为max{|x|, |y|}，问题得解。完整程序（C++11）如下：

本题代码参考了http://www.cnblogs.com/AOQNRMGYXLMV/p/4202527.html。

习题10-4　素数间隔（Prime Gap，ACM/ICPC Japan 2007，UVa1644）

输入一个整数n，求它后一个素数和前一个素数的差值。输入是素数时输出0。n不超过1299709（第100000个素数）。例如n＝27时输出29-23＝6。

【分析】

首先筛选出符合条件的所有素数，存在一个vector＜int＞ primes中。对于n来说，令pl＝lower_bound（primes．begin（），primes．end（），n）。pl就指向第一个大于等于n的素数。如果*pl＝N，则说明N是素数；否则pl-1指向最后一个小于n的素数。

习题10-5　不同素数之和（Sum of Different Primes，ACM/ICPC Yokohama 2006，UVa1213）

选择K个质数，使它们的和等于N。给出N和K（N≤1120，K≤14），问有多少种满足条件的方案？例如n＝24，k＝2时有3种方案：5＋19＝7＋17＝11＋13＝24。注意，1不是素数，因此n＝k＝1时答案为0。

【分析】

首先需要筛选出所有可能符合条件的素数。之后这个问题就转换成一个背包问题：

（1）d（i，n，k）表示从第i个及其以后的素数中选择k个素数其和为n的方案个数。

（2）递推公式就是：d（i，n，k）＝d（i＋1，n，k）＋d（i＋1，n-p_i，k-1），分别对应是否使用第i个素数p_i的策略。

边界条件如下：

（1）n＜2或者p_i＞ n时，则d＝0。

（2）k＝1时，如果n是素数，则d＝1，否则d＝0。

习题10-6　连续素数之和（Sum of Consecutive Prime Numbers，ACM/ICPC Japan 2005，UVa1210）

输入整数n（2≤n≤10000），有多少种方案可以把n写成若干个连续素数之和？例如输入41，有3种方案：2＋3＋5＋7＋11＋13、11＋13＋17和41。

【分析】

首先筛选出所有符合条件素数组成的序列P，然后求出P的前缀和序列PS，则所求结果就是符合条件“PS［i］＋n依然在PS中”的i的个数。

习题10-7　几乎是素数（Almost Prime Numbers，UVa10539）

输入两个正整数L、U（L≤U≤10¹²），统计区间［L，U］的整数中有多少个数满足：它本身不是素数，但只有一个素因子。例如4和27都满足条件。

【分析】

这种数的唯一分解中一定只包含一个素数：p^k，其中k≥2，记n ，则显然有p≤n。我们对素数筛法进行改造：每发现一个素数p就把所有的p^k（k≥2且p^k≤10¹²）记录下来。最后按照从小到大的顺序把这些数字记录下来存放到一个vector中，记为aps。

对于区间［L，U］，第一个大于等于L的数就是lower_bound（aps．begin（），aps．end（）），第一个大于U的数就是upper_bound(aps.begin(), aps.end(), U)，则这两个位置形成一个左闭右开区间，区间中数字的个数即是所求的结果。

和《算法竞赛入门经典（第2版）》中的第10.1.2节类似，虽然内循环多了一个步骤，但这个步骤的循环次数的最大值为log_p(10¹²) ≈39，整体的算法复杂度为O(nlogn)。完整程序（C++11）如下：

习题10-8　完全P次方数（Perfect Pth Powers, UVa10622）

对于整数x，如果存在整数b使得x=b^p，我们说x是一个完全p次方数。输入整数n，求出最大的整数p，使得n是完全p次方数。n的绝对值不小于2，且n在32位带符号整数范围内。例如n=17, p=1；n=1073741824, p=30；n=25, p=2。

【分析】

对于x是正数的情况，首先求出x的唯一分解p1^k1p2^k2、…、pn^kn。如果x是一个全p次方数，则所有的ki必然都是p的倍数，然后求所有ki的最大公约数就是p。

需要注意的是，如果x是负数，则p不能是偶数，所以求出所有ki的最大公约数之后，还要把其中的2除尽才得到p。

习题10-9　约数(Divisors, UVa294)

输入两个整数L和U（1≤L≤U≤10⁹，U-L≤10000），统计区间[L,U]的整数中哪一个的正约数最多。如果有多个，输出最小值。

【分析】

对于整数K来说，假设其唯一分解为Π，则约数个数为Πk_i。可以用筛法先求出所有1～10⁵之间的素数，然后对L, U之间的整数进行唯一分解并且遍历，即可求出结果。

习题10-10　统计有根树（Count, Chengdu 2012, UVa1645）

输入n（n≤1000），统计有多少个n结点的有根树，使得每个深度中所有结点的儿子数相同。例如n=4有3棵，如图2.63所示；n=7时有10棵。输出数目除以10⁹+7的余数。

【分析】

令A[n]为所求的值，首先对于n=1,2来说A[n]=1。根据题意，一个结点的所有子树结构都必须完全一致，则对n个结点数的子树的结点个数j进行遍历就可以得出： ，其中n-1能被j整除。注意要使用long long，防止数据溢出。

习题10-11　圈图的匹配（Edge Case, ACM/ICPC NWERC 2012, UVa1646）

n（3≤n≤10000）个结点组成一个圈，求匹配（即没有公共点的边集）的个数。例如n=4时有7个（如图2.64所示），n=100时有792070839848372253127个。

【分析】

首先看另一个问题，令F[n]为n个点组成线段链（不连成圈）中匹配的个数，则F[1]=1，F[2]=2，F[3]=3。考虑第n-1个线段是否在匹配中：如果在，则线段n-2不在，故有F[n-2]个匹配；否则有F[n-1]个匹配。由此可得F[n]=F[n-1]+F[n-2]，其实就是斐波那契数列。

回到本题，记所求匹配数为C[n]，根据点1和点2之间的线段是否在匹配中两种情况，可得C[n]=F[n]+F[n-2]。递推计算即可。注意，本题中的结果连long long（64位整数）也放不下，需使用大整数类。

习题10-12　汉堡（Burger, UVa557）

有n个牛肉堡和n个鸡肉堡给2n个孩子吃。每个孩子在吃之前都要抛硬币，正面吃牛肉煲，反面吃鸡肉煲。如果剩下的所有汉堡都一样，则不用抛硬币。求最后两个孩子吃到相同汉堡的概率。

【分析】

在正面或者背面的次数达到n次之后，就会出现符合题意的条件。但是情况太多，分类计数很麻烦，从另外一个角度来考虑，如果扔的前2n-2次，正面和反面出现的次数一样多，则最后两个孩子就会吃到不同的汉堡，记这种情况出现的概率为F_n，则所求结果为1-F_n，且有 。但是分式的上下两项直接计算的话，必然会溢出。可从上述公式进一步得到F_n的递推公式： ，直接递推计算即可。

习题10-13　H(n)（H(n), UVa11526）

输入n（在32位带符号整数范围内），计算下面C++函数的返回值：

例如n=5, 10时，答案分别为10和27。

【分析】

以n=10为例，i=1～10时累加的数字依次是10, 5, 3, 2, 2, 1, 1, 1, 1, 1。有5个1，2个2，1个3…。

由此考虑n/i=1时，i的范围，显然是n/2<i≤n/1，就有（n/1-n/2）个1。

n/i=2时，n/3<i≤n/2，就有（n/2-n/3）个2。

n/i=3时，n/4<i≤n/3，就有（n/3-n/4）个3。

…

n/i=k时，n/(k+1)<i≤n/k，有（n/(k+1)-n/k）个k。

需要注意的是，当开始，就按照正常的n/i计算。此时有 。算法的时间复杂度就是 。主循环逻辑如下：

注意n<0时循环不会运行，直接返回0。

习题10-15　零和一（Zeros and Ones, ACM/ICPC Dhaka 2004, UVa12063）

给出n, k（n≤64，k≤100），有多少个n位（无前导0）二进制数的1和0一样多，且值为k的倍数？

【分析】

使用D(z,o, m)表示符合以下条件的数字的个数：

（1）以1开头。

（2）1后面共有z个0，o个1。

（3）除k的余数为m。

则边界条件为D(0,0,1)=1。每个二进制数后面每附加一个数字就有两种转移方式：

（1）D(z+1,o, (m*2)%k)+=D(z,o,m) //后面附加一个0

（2）D(z,o+1, (m*2+1)%k)+=D(z,o,m) //后面附加一个1

当n为奇数或k=0时无解。当n是偶数时，所求答案为：D(n/2, n/2-1,0)。

习题10-16　计算机变换（Computer Transformations, ACM/ICPC SEERC 2005, UVa1647）

初始串为一个1，每一步会将每个0改成10，每个1改成01，因此1会依次变成01, 1001, 01101001, …输入n（n≤1000），统计n步之后得到的串中，“00”这样的连续两个0出现了多少次。

【分析】

我们分析所有可能的变换：

0→10

1→01

00→1010

10→0110

01→1001

11→0101

记F_n为第n步之后的00的个数，由前文所示，00是由01得到的，只需知道n-1步后01的个数E_n-1就得到F_n。再看前文推导，01由1和00得到，而第n步后1的个数是2^n-1,所以F_n=E_n-1=2^n-3+F_n-2，由此直接递推即可。注意n≤1000，所以必须使用高精度整数运算。

习题10-17　H-半素数（Semi-prime H-numbers, UVa11105）

所有形如4n+1（n为非负整数）的数叫H数。我们定义1是唯一的单位H数，H素数是指本身不是1，且不能写成两个不是1的H数的乘积。H-半素数是指能写成两个H素数的乘积的H数（这两个数可以相同，也可以不同）。例如25是H-半素数，但125不是。

输入一个H数h（h≤1000001），输出1到h之间有多少个H-半素数。

【分析】

参考素数筛法，用vis[i]记录4i+1是否是H-素数。对于每个整数i（4i+1不是H-素数），令h_i=4*i+1，对于所有的j=(k*h_i)*h_i（k≥h_i），如果j%4=1，则说明j不是h素数，记vis[(j-1)/4]=1。否则记录h_i为H-素数。筛法部分外层循环的次数为n，给定外层的循环变量，内层循环的次数小于。所以参考《算法竞赛入门经典（第2版）》10.1.2节的时间复杂度分析可以得出，本题筛法部分的时间复杂度上限依然为O(nlogn)。

筛出所有的H素数之后，两两相乘将所有的乘积记录下来，注意可能重复，然后用一个cnt[N]数组记录H半素数的个数，其中cnt[i]表示1到4i+1之间所有的H半素数的个数，用O(n)的时间就可以将cnt处理完成。这样问题的解就是 。完整程序如下：

习题10-18　一个研究课题（A Research Problem, UVa10837）

输入正整数m（m≤10⁸），求最小的正整数n，使得φ(n)=m。输入保证n小于200000000。

【分析】

记N=200000000。假设p₁, p₂…p_k为n的素因子，则，注意其中的m_i有可能为0。且如果，m_k一定为1。

首先筛选出所有小于的素数。然后对于n，遍历所有不大于的素数p，如果φ(n)能被p-1整除，则p有可能是n的素因子，但出现在n的唯一分解中的次数未知。

然后对所有可能是n的素因子的p的次数进行回溯，每一步尝试p的次数为0,1,2…，在φ(n)除去相应的p^m以及(p-1)。最后当所有可能素数决策完之后，φ(n)还可能没除干净，剩余一个x，此时就要判断x+1是未被使用过的素数，如果是，则说明我们得到了一个合法的n。完整程序（C++11）如下：

习题10-19　蹦极（Bungee Jumping, UVa10868）

007为了摆脱敌人的追击，逃到了一座桥前。桥上正好有一条蹦极绳，于是他打算把它拴到腿上，纵身跳下桥，落地后切断绳子，继续逃。已知绳子的正常长度为l，Bond的体重为w，桥的高度为s，你的任务是替007判断能否用这种方法逃生。

当从桥上跳下后，绳子绷紧前Bond将做自由落体运动（重力按9.81w计），而绷紧后绳子会有向上的拉力，大小为k*Δl，其中Δl为绳子当前长度和正常长度之差。当且仅当Bond可以到达地面，且落地速度不超过10米/秒时，我们才认为他安全着落。

输入每组数据包含4个非负整数k、l、s、w（s<200）。对于每组数据，如果可以安全着地，输出“James Bond survices.”，如果到不了地面，输出“Stuck in the air.”，如果到达地面速度太快，输出“Killed by the impact.”。

【分析】

弹簧弹力和Δl的关系是一个三角形（如图2.65所示），弹簧伸长的长度从0到Δl，对Bond做的功刚好是这个三角形的面积，即k*Δl²/2。

记v为触底的速度，根据动能定理，合外力对物体所做的功，等于物体动能的变化，，因此有，其中L=s-l，s< l时L=0。针对v²的值分情况讨论：

（1）如果v²≤0，说明卡在半空。

（2）如果v²≤100，说明安全着陆。

（3）否则说明触底速度大于10，摔死了。

习题10-20　商业中心（Business Center, NEERC 2009, UVa1648）

商业中心是一幢无限高的大楼。在一楼有m座电梯，每座电梯只有两个键：上、下。对于第i座电梯，每按一次“上”会往上走u_i层楼，每按一次“下”会往下走d_i层楼。你的任务是从一楼开始选一个电梯，恰好按n次按钮，到达一个尽量低（一楼除外）的楼层。中途不能换乘电梯。1≤n≤1000000，1≤m≤2000，1≤u_i，d_i≤1000。

【分析】

不妨设对于每一个电梯，向上按了a次，向下按了b次，则a+b=n，则这个电梯最终停靠的层数就是m=a*u-b*d=a*(u+d)-n*d。本题就是要对每个电梯求m的最小正整数值。这个最小值，就是在a=n*d/(u+d)+1时取得，这里的除法就是整数除法。

最终的答案就是所有电梯的m的最小值。注意，此题需使用long long。

习题10-23　Hendrie序列（Hendrie Sequence, UVa10479）

Hendrie序列是一个自描述序列，定义如下：

（1）H(1)=0。

（2）如果把H中的每个整数x变成x个0后面跟着x+1，则得到的序列仍然是H（只是少了第一个元素）。

因此，H序列的前几项为0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...。输入正整数n（n<2⁶³），求H(n)。

【分析】

可以将H序列分块，写出H序列的前几块（第0块特殊），如表2.2所示。

同时可以发现第m块由以下序列组成：

1个第m-2块

2个第m-3块

...

m-1个第0块

m

根据以上规律，对于一个输入数字n，首先让n=n-1（因为使用以0为起始下标统计更方便）。然后根据上述规律，找到n所在的那个块m，并且找到n在m块中的位置。如果正好是块结尾，直接返回m即可。如果不是，找到n所属的子块以及在子块中的位置，递归计算即可。完整程序如下：

习题10-28　数字串（Number String, ACM/ICPC Changchun 2011, UVa1650）

每个排列都可以算出一个特征，即从第二个数开始每个数和前面一个数相比是增加（I）还是减少（D）。例如{3,1,2,7,4,6,5}的特征是DIIDID。输入一个长度为n-1（2≤n≤1001）的字符串（包含字符I、D和?），统计1～n有多少个排列的特征和它匹配（其中?表示I和D都符合）。输出答案除以1000000007的余数。

【分析】

参考LCS等字符串相关的DP问题，不难想到把排列长度以及最后一位数字考虑进去作为状态考虑：记dp(i,j)为由数字1～i组成的排列中，以j结尾的符合指定特征的排列个数。但是确定最后一位之后发现，前面的1～i-1位并不是1～i-1组成的排列，而是{1,2…j-1, j+1…i}组成的排列，无法进行状态转移。而且n又比较大，无法简单地用一个位向量来表示这个排列。

观察{3,1,2,7,4,6,5}，将其中所有大于4的数字加1，转换成由{1～4,6～8}组成的排列{3,1,2,8,4,7,6}，其特征字符串依然是DIIDID。不难由此推广出以下结论：给定一个长度为i的特征字符串，由{1,2,…,i}组成的匹配排列和由{1,2,…,j-1,j+1,…,i+1}组成的匹配排列一一对应。这样就可以进行先进行等价转换，再状态转移。

按照i=1～n的顺序对第i位的数字进行决策，决策时，把{1,2,…j-1,j+1,…i}的排列转换为{1,2…i-1}的排列，则状态转移可以分3种情况来讨论：

（1）s[i]=='I'，则第i-1位必须小于j，于是有dp(i,j)=dp(i-1,1)+dp(i-1,2)+…+dp(i-1,j-1)=

（2）s[i]=='D'，则j之前就是以j+1～i其中之一为结尾的{1,2…j-1, j+1…i}的排列，也就是以j～i-1为结尾的{1,2…i-1}的排列，dp(i, j)=dp(i-1, j)+dp(i-1, j+1)+…+dp(i-1,i-1)=

（3）s[i]=='?'，则dp(i,j)=dp(i-1,1)+dp(i-1,2)+…+dp(i-1,i-1)=dp(i-l,k)。

观察以上的状态转移方程，不难想到引入sum(i,j)dp(i,k)，则上述的状态转移就简化成：

（1）s[i]=='T'，dp(i,j)=sum(i-1,j-1)。

（2）s[i]=='D'，dp(i,j)=sum(i-1,i-1)-sum(i-1,j-1)。

（3）s[i]=='?'，dp(i,j)=sum(i-1,i-1)。

初始条件为sum(1,1)=dp(1,1)=1，剩下的按照i从小到大,j从1到i，依次求dp(i,j)之后更新sum(i,j)。这样通过引入sum(i,j)，时间复杂度就从O(n³)变成O(n²)。完整程序如下：

习题10-37　倍数问题（Yet Another Multiple Problem, Chengdu 2012, UVa1653）

输入一个整数n（1≤n≤10000）和m个一位十进制数字，找n的最小倍数，其十进制表示中不含这m个数字中的任何一个。

【分析】

简单的暴力做法，就是从最左边开始逐位使用所有的可用数字尝试构造，看看能不能整除n。但是这样算法复杂度是指数级的，必然会超时。仔细观察不难发现，每构造一位，除n的余数就会发生变化。把模n的每个余数作为一个结点，每构造一位就是沿着这张图走一步，则本题实际上就是求到结点0的最短路径，使用BFS非常合适。

具体来说，建一张图，结点i代表除以n的余数等于i，然后每次附加一位数字就进行状态转移，转移是基于模运算：(10*a+b)mod n=(amod n)*10+bmod n。那么主要的搜索逻辑就是从可用数字开始，搜索到结点0的最短路径。另外，每扩展出一个结点，都记录下结点前驱以及引起这次状态转移的数字，方便最终输出结果。另外本题的BFS过程使用结点前驱判重，如果已经有前驱结点，则不再继续搜索。

举例来说，考虑n=14，m=3，3个禁用的数字分别是7、8和4。为方便讨论起见，加入一个虚拟的根结点x，表示根结点，则一开始附加所有可用的数字（1,2,3,5,6,9，参见图2.66中边上的数字）。一开始就建立从x到每个数字对应的余数结点的所有边。然后每个余数结点再添加一位进行状态转移，直到搜索出从x到0结点的最短路径。最短路径上每条边上的数字拼接起来就是所求的数字。

算法的时间复杂度为O(n)，完整程序（C++11）如下：

习题10-38　正多边形（Regular Polygon, UVa10824）

给出圆周上的n（n≤2000）个点，选出其中的若干个组成一个正多边形，有多少种方法？输出每行包含两个整数S和F，表示有F种选法得到正S边形。各行应按S从小到大排序。

【分析】

一个圆上的正K边形的顶点把圆分成K个角度相等的弧。从其中一个顶点就可以得到其他所有的顶点。

回到本题，输入时将每个点转换为弧度，然后排序。之后遍历所有的多边形顶点数F，尝试从每个点出发构造一个正F边形，构造成功就记录下来。注意任何一个点都记录一下曾经判断过的以其为顶点的多边形的顶点数，避免重复判断。算法的时间复杂度为O(n³*log(n))。完整程序（C++11）如下：

习题10-39　圆周上的三角形（Circum Triangle, UVa11186）

在一个圆周上有n（n≤500）个点。不难证明，其中任意3个点都不共线，因此都可以组成一个三角形。求这些三角形的面积之和。

【分析】

三角形的面积都可以通过圆的面积减去3个弓形（图2.67左边的圆中的灰色部分）的面积得出。那么所有三角形的面积之和就可以如下计算：个圆面积–所有的三角形对应的弓形面积之和。

首先对于所有输入的点，将其转换为弧度，然后进行递增排序存到一个数组A[n]中。而对于每两个弧度i和j（i<j且A_i<A_j）来说，i到j之间会有j-i-1个点，也就是说，会有j-i个顶点在ij上方，并且以弦ij为底的三角形。也就是说，弦ij下方的弓形面积会在上述公式中出现j-i-1次。而同理可知弦ij上方的弓形会出现n-2-(j-i-1)次。记a=A_j-A_i，则上方的弓形面积是 。下方的弓形面积就是πR²-S。二者的面积分别乘以出现次数再加起来就是：

S(n-2-（j-i-l）)+（j-i-l）(πR²-S)=S（n-2j+2i）+（j-i-l）πR²

首先令 ，遍历每一对i<j，然后在sum上减去上述结果即可。注意当n<3时，sum=0。而且可以先当作单位圆计算，令R=1，输出时再乘以R²即可。时间复杂度为O(n²)。完整程序（C++11）如下：

习题10-40　实验法计算概率（Probability Through Experiments, ACM/ICPC Hatyai 2012, UVa12535）

输入圆的半径和圆上n（n≤20000）个点的极角，任选3点能组成多少个锐角三角形？

【分析】

如图2.68所示，圆上的三角形，按顺时针方向记其顶点为A、B、C。如果是钝角三角形，则圆周上A到C的角AOC<180°。如果是直角三角形，则AOC=180°，B在A、C之间。如果是锐角三角形，则AOC>180°。显然判断锐角三角形更麻烦些，所以可以使用排除法，求出所有三角形的个数减去直角和钝角三角形的个数即可。

输入之后按弧度θ排序，为了方便处理，点集中要加入所有的θ+360。遍历所有的极角A，然后查找所有的符合A<B<C≤A+180的B和C的个数。如果A到A+180中有M个点，则在总的三角形个数N(N-1)(N-2)/6中减去M(M-1)/2。完整程序（C++11）如下：

习题10-42　网格中的三角形（Triangles in the Grid, UVa12508）

一个n行m列的网格有n+1条横线和m+1条竖线。任选3个点，可以组成很多三角形。其中有多少个三角形的面积位于闭区间[A,B]内？1≤n, m≤200，0≤A<B≤nm。

【分析】

直接枚举三角形会非常麻烦，但是考虑到三角形的顶点都在横线和竖线的交点上，不难想到每个这种三角形都有一个最小包围矩形。那么首先是按照长宽来遍历这种矩形的个数，考虑矩形的左上角坐标以及长宽即可。因为三角形的面积在计算时都要除以2，所以可以事先把A和B乘以2，然后在计算三角形面积时就不除了，同时也避免计算误差。

对于一个长宽为(r,c)的矩形cell来说，不妨对如图2.69所示的矩形的顶点做如下标记：

其包围的三角形可以分为以下几种情况，如图2.70所示。

（1）3个顶点都在cell顶点上，共4种，面积都是r*c。

（2）只有两个顶点在cell顶点上，这两个顶点相邻，则第三个顶点在对边上。对第三个顶点进行计数可以得出这种三角形的个数为2*(r-1)+2*(c-1)。

（3）有两个顶点形成对角线，另外的顶点在水平边上。不妨设水平的那条边长度为i，则i就需要满足：A≤r*i≤B且1≤i< c– 1-> r≤r*i< r*(c-1)，也就是说max(A,r)≤r*i≤min(B,r*c-r)。符合这个不等式的i的个数乘以4就是这种情况下的三角形个数。

（4）跟上述情况类似，有两个顶点形成对角线，另外的顶点在垂直边上。不妨设垂直的那条边长度为i，则这种情况下三角形的个数就是符合以下不等式的i的个数乘以4：max(A,c)≤c*i≤min(B, r*c-c)。

（5）有两个顶点形成对角线，另外的顶点在矩形内部。令第三个顶点的坐标为(i,j)，意思是离边AB的距离为i，离AD的距离为j。那么遍历所有的i=1～r-1，当i确定时j就需要满足：r*c-B-col * i≤r* j≤r*c-A-Col * i。就是要计算符合此条件的j的个数然后乘以4（对称性考虑）。

（6）只有一个顶点在四角上，另外两个点肯定都在跟这个点不相邻的边上。不妨设这个顶点就是A，则另外两个顶点一定在CD和BC上，不妨设在CD上的顶点离D的距离为i，在BC上的顶点距离B为j。则三角形的面积为：2rc-(i*c+j*r+(r-i)*(c-j))=r*c-i*j，遍历所有的i=1～r-1，对于指定的i，j就要满足A≤r*c– i*j≤B→ r*c-B≤i*j≤r*c–A以及1≤j≤c– 1 → i≤i*j≤i*(c-1)，那么符合max(r*c-B,i)≤i*j≤min(r*c-A, i*(c-1))这个不等式的j的个数乘以4就是符合这种情况的三角形个数。

遍历所有的r和c，大小为(r,c)的矩形个数就是(n-r+1) * (m-c+1)。对这些矩形分别进行三角形计数并且加起来就是最终所求的三角形个数。

需要注意的是，各种情况都牵涉求符合形如L≤K*X≤R的不等式的X的个数，可以将这个过程提取出来复用。完整程序如下：

习题10-43　整数对（Pair of Integers, ACM/ICPC NEERC 2001, UVa1654）

考虑一个不含前导零的正整数X，把它去掉一个数字以后得到另外一个数Y。输入X+Y的值N（1≤N≤10⁹），输出所有可能的等式X+Y=N。例如N=34有两个解：31+3=34；27+7=34。

【分析】

记n的十进制表示形式的长度为L，不妨设从X右边数第i（0≤i<L）位删除数字x（0≤x<10）得到Y（如图2.71所示），记X=a*10ⁱ⁺¹⁺x*10ⁱ+b，b<10ⁱ，则Y=a*10ⁱ+b。X+Y=n，故有11*a*10ⁱ+x*10ⁱ+2*b=N。

遍历所有的i和x，固定i和x之后，求不定方程11*a*10ⁱ+2*b=N-x*10ⁱ的所有满足a≥0且0≤b<10ⁱ整数解(a,b)，直接计算并输出X和Y即可。完整程序（C++11）如下：