Uva(1393)(Highways)

链接：https://vjudge.net/problem/UVA-1393
思路：代码很短，但是却不好想，首先我们要考虑如果确定两点怎么判断他们能否形成一条之前没有重复过的直线，方法就是看他的向量的gcd是否为1，不为1则前面肯定计算过，所以我们考虑预处理的时候用dp[i][j]表示向量(x,y)(x<y,y<j)一共有多少个是互质的，则递推式为 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (gcd(i,j)==1)，接下来我们处理所有点，当到点(i,j)时，内部各点与他组成的向量范围都在[1,i-1][1,j-1]内，那么可以用dp[i-1][j-1]表示其中有多少与其互质，但是会有重复计算的，我们思考一下重复计算的是哪些，必定是向量间满足二倍关系的（上面一半计算了一次，下面一半又计算了一次），所以再减去dp[(i-1)/2][(j-1)/2]即可，为了方便书写我们把所有i，j都+1，最后答案的时候找对应n-1的值即可
代码

#include<bits/stdc++.h>
using namespace std;

int n,m;
long long dp[305][305];
long long ans[305][305];

int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}

int main(){
    for(int i=1;i<=300;i++){
        for(int j=1;j<=300;j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (gcd(i,j)==1);
        }
    }
    for(int i=1;i<=300;i++){
        for(int j=1;j<=300;j++){
            ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] +  dp[i][j] - dp[i/2][j/2];
        }
    }
    while(scanf("%d%d",&n,&m)&&(n||m)){
        printf("%lld\n",ans[n-1][m-1]*2);
    }
    return 0;
}