紫书例题 10-28 UVa 1393（简化问题）-白红宇

紫书例题 10-28 UVa 1393（简化问题）

阅读量：681 次

发布时间：2019-03-17

本文共 1119 字，大约阅读时间需要 3 分钟。

如何优化给定的文字：

问题分析与解决思路

这道题目具有对称特性，因此只需计算特定边界条件下的数目，并将结果乘以2即可。

1.1 包围盒分析

每一条直线可以看作一个包围盒，需要枚举包围盒的长宽。分析时需注意以下两种情况：

1.2 情况分析

（1）包围盒内部存在其他包围盒。这种情况下，只有在包围盒交点处且包围盒对角线不重合的情况下，需要单独计算。通过计算gcd值来判断是否为唯一交点。

（2）特殊情况处理：对角线落在一条直线上时，需要减去重复计数的数目。这时数目计算公式为：max(0, m - 2a) * max(0, n - 2b)最终数目为：(m - a) * (n - b) - max(0, m - 2a) * max(0, n - 2b)

1.3 代码实现

为了加快计算，提前预先计算所有gcd值并存储。通过预计算降低重复调用gcd函数的开销。主要代码实现步骤如下：

#include 
   
    #include 
    
     #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 312;int g[MAXN][MAXN];int gcd(int a, int b) {    return !b ? a : gcd(b, a % b);}int main() {    REP(i, 1, MAXN)        REP(j, 1, MAXN)            g[i][j] = gcd(i, j);        while (scanf("%d%d", &n, &m) && n) {        int ans = 0;        REP(a, 1, m + 1)            REP(b, 1, n + 1) {                if (g[a][b] == 1) {                    int c = max(0, m - 2*a) * max(0, n - 2*b);                    ans += (m - a) * (n - b) - c;                }            }        printf("%d\n", ans * 2);    }    return 0;}