[BZOJ 2987][クラスユークリッドアルゴリズム]Earthquake

題意
Ax+By=Cの非負の整数解の個数を求めます。
クラスヨーロッパのテンプレートの問題
Σax+bcという形になりましたが、Manchery大神さんの手押しが見られます。http://blog.csdn.net/u014609452/article/details/52343530

#include 
#include 
#include 
#include 

using namespace std;

typedef long long ll;

ll a,b,c;

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

#define T ((-b+c-1)/c)
#define N ((a*n+b)/c)

ll solve(ll n,ll a,ll b,ll c){
    if(!a) return (b/c)*n;
    if(b<0) return solve(n,a,b+T*c,c)-T*n;
    if(b>=c) return solve(n,a,b%c,c)+(b/c)*n;
    if(a>=c) return solve(n,a%c,b,c)+((a/c)*n*(n+1)>>1);
    return (n+1)*N-solve(N,c,-b+a-1,a);
}

int main(){
    cin>>a>>b>>c;
    printf("%lld
",(c/a)+(c/b)+solve(c/a,a,c%a-a,b)+1);
}