百度之星初赛一 1003

题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=6745

写这道题的时候一直tle，结果发现是因为用的是cin却在a完上一题把cin.tie(0)和ios::sync_with_stdio(0)不小心删了。。。直到结束后才发现

思路：举个例子 求（a，b）逐步减一到两者均为一时一共有多少次互质可以看作 ans(a,b)=max((a-1,b),(a,b-1))+1。（加一的前提是（a，b）互质）。

#include <bits/stdc++.h>
#include <cassert>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int w[10005],c[10005];
int ans,v;
int f[1005][1005],g[1005][1005];
int gcd(int a,int b)
{
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    int t; int ans;cin >> t;
    f[1][1]=1;g[1][1]=1;
    for(int i=1;i<=1000;i++)
    {
        for(int j=1;j<=1000;j++)
        {
            if(i==1) f[i][j]=f[i][j-1]+1;
            else if(j==1)
            f[i][j]=f[i-1][j]+1;
            else
            {
                if(gcd(i,j)==1)
                {
                    f[i][j]=max(f[i-1][j],f[i][j-1])+1;
                }
                else f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
        }

     }
    while(t--)
    {
       int a,b; 
       cin >> a >>b;
       printf("%d\n",f[a][b]);
    }
    return 0;
}