hdu6745(渐减1过程的最多互质对数，dp)

题：http://acm.hdu.edu.cn/showproblem.php?pid=6745

题意：给定a，b，可执行操作a-1或b-1（前提a>1,b>1）问这过程中最多的互质次数是多少；

分析：询问T较多，预处理dp，dp[i][j]表示从i和j 开始的最多互质对数，dp[i][j]是由dp[i-1][j]和dp[i][j-1]转化而来

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e10;
int dp[1003][1003];
void init(){
    for(int i=1;i<=1000;i++)
        dp[i][1]=dp[1][i]=i;
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++){
            dp[i][j]=(__gcd(i,j)==1)+max(dp[i-1][j],dp[i][j-1]);
        }
}
int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d
",dp[a][b]);
    }
    return 0;
}