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 = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;

     for(x = ; isdigit(c); c = getchar()) x = x *  + c - '';

     if(f) x = -x;

     return x;

 }

 template<typename Q> Q read() {

     static Q x; read(x); return x;

 }

 const int N =  + ;

 int g[N][N];

 int main() {

 #ifdef DEBUG

     freopen("in.txt", "r", stdin);

     freopen("out.txt", "w", stdout);

 #endif

     for(int i = ; i <= ; i++) {

         for(int j = i; j <= ; j++) {

             g[i][j] = g[j][i] = __gcd(i, j);

         }

     }

     int n, m;

     while(scanf("%d%d", &n, &m), n) {

         int ans = ;

         for(int a = ; a <= m; a++) {

             for(int b = ; b <= n; b++) {

                 if(g[a][b] == ) {

                     int c = max(, m - (a << )) * max(, n - (b << ));

                     ans += (m - a) * (n - b) - c;

                 }

             }

         }

         printf("%d\n", ans << );

     }

     return ;

 }