uva1393 Highways

留坑(p.339) 已填（膜汪）

每条直线至少经过两个点，我们不妨在经过的所有点中的第二个点统计它

设f[i][j]表示i * j的答案，那么显然可以用f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + 以(i, j)这个点为第二个经过的点的直线

这样的直线的数量与(1, 1) ~ (i - 1, j - 1)中与(i, j)横纵坐标差与(i, j)互质的点的数量有关（还要再减掉一写）

而这个数量等于(1, 1) ~ (i - 1, j - 1)中与(0, 0)横纵坐标差与(i, j)互质的点的数量

具体的参照http://blog.csdn.net/accelerator_/article/details/26132853

预处理时间复杂度O(n²)后可以做到O(1)回答询问

 

rjl的算法：枚举有效包围盒的数量

这样每次都是O(n²)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>

using namespace std;

void setIO(const string& s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
template<typename Q> Q read(Q& x) {
    static char c, f;
    for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;
    for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    if(f) x = -x;
    return x;
}
template<typename Q> Q read() {
    static Q x; read(x); return x;
}

const int N = 300 + 10;

int g[N][N];

int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    
    for(int i = 1; i <= 300; i++) {
        for(int j = i; j <= 300; j++) {
            g[i][j] = g[j][i] = __gcd(i, j);
        }
    }
    
    int n, m;
    while(scanf("%d%d", &n, &m), n) {
        int ans = 0;
        for(int a = 1; a <= m; a++) {
            for(int b = 1; b <= n; b++) {
                if(g[a][b] == 1) {
                    int c = max(0, m - (a << 1)) * max(0, n - (b << 1));
                    ans += (m - a) * (n - b) - c;
                }
            }
        }
        printf("%d
", ans << 1);
    }
    
    return 0;
}