SPOJ4717——Grid Points in a Triangle

题目的意思很简单。就是要你求出斜率为a/b的一个点在原点，一条边为x=n的RT三角形里面有多少个整数点？

看完题目后依然没有思路，依然去看各个神牛写的题解。后来才反应过来。

题目的正解应该是这样的。递归求解。

假如对于当前dfs(n,a,b)表示我们要求解斜率为a/b，且横坐标不超过n的整点数目。

如果a>b，那么我们可以统计在在内部包含的点数为=a/b个等腰直角三角形所包含的点的数目+dfs(n,a%b,b)。

好好理解上面这个式子，这也算是第一个难点吧。

 d=a*n/b;

至此，我们可以保证a<b了，于是我们把三角形补全为平行四边形，这样相当于递归求dfs(d,b,a)了。

但是中间有一些难点细节，比如其实对于整点数目来说，平行四边形按对角线平分为两个直角三角形中的整点数目不一定是相等的，而且还有对角线上面的点重复添加了，所以要考虑减出来，减多了的又要加回去。详见代码：跟神犇的很相似，诶，数论嘛。

#include <cstdio>
#define ll long long
using namespace std;

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

ll dfs(ll n,ll a,ll b)
{
    ll t=n*(n+1)/2*(a/b);
    a%=b;
    if (a==0) return t+n+1;//a==0说明与x轴重合了，点数为n+1。原来还要考虑有多少倍等腰直角三角形的点数。
    ll d=a*n/b;
    t+=(n+1)*(d+1)+d/a+1;//平行四边形另一半减多了的要加回来。
    return t-dfs(d,b,a);//减去四边形中另一半的点数。
}

int main()
{
    ll a,b,n,t,g;
    scanf("%lld",&t);
    while (t--)
    {
        scanf("%lld%lld%lld",&n,&a,&b);
        g=gcd(a,b);
        printf("%lld
",dfs(n,a/g,b/g));//如果不除以gcd，答案会出错。
    }
    return 0;
}