湘潭大学四月月赛C题A+B(扩展欧几里得定理)

//a和b不一定要有，fuck!!!
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

//不用int64就可以A的
__int64 exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    __int64 g=exgcd(b,a%b,x,y);
    __int64 temp=x;
    x=y;
    y=temp-(a/b)*y;
    return g;
}

__int64 gcd(__int64 m,__int64 n)
{
    while(n)
    {
        __int64 tmp=m%n;
        m=n;
        n=tmp;
    }
    return m;
}

__int64 mi(__int64 m,__int64 n)
{
    if(m>n) return n;
    return m;
}

__int64 ma(__int64 m,__int64 n)
{
    if(m>n) return m;
    return n;
}

int main()
{
    __int64 a,b,s,d;
    while(~scanf("%I64d%I64d%I64d",&a,&b,&s))
    {
        __int64 x,y;
        d=gcd(a,b);
        if(s%d!=0)
        {
            puts("0");
            continue;
        }
        else if(a+b>s)
        {
            puts("0");
            continue;
        }
        else if(a==b)
        {
            if(s%a==0)
                puts("1");
            else puts("0");
            continue;
        }

        a=a/d,b=b/d,s=s/d;
        __int64 tt=exgcd(a,b,x,y);

        //现在的x,y是ax+by=1的一个解
        x=x*s,y=y*s;
        //现在的xy是ax+by=s的一个解

        __int64 cnt=0;
        //__int64 s1,s2;

        //根据x,y的值来判断到底有多少可行解
        //因为ax+by=s，所以a(x+nb)+b(y-na)=s也是可行解，所以直接找n的值使得x+nb与y-na都为正数或0即可

        //代码写搓了。。
        /*if(x<=0&&y>=0)  //okok
        {
            x=-x;
            if(x%b==0) s1=x/b;
            else s1=x/b+1;

            if(y%a==0) s2=y/a;
            else s2=y/a;
        }
        else if(y<=0&&x>=0)  //okok
        {
            y=-y;
            if(y%a==0) s1=y/a;
            else s1=y/a+1;

            if(x%b==0) s2=x/b;
            else s2=x/b;
        }
        else if(x>0&&y>0)  //ok
        {
            s1=-x/b;
            s2=x/b;
            s1=ma(s1,-y/a);
            s2=mi(s2,y/a);
        }
        else
        {
            puts("0");
            continue;
        }*/
        x=x%b;
        if(x<0) x+=b;
        y=(s-a*x)/b;   //解出a(x+nb)+b(y-na)=s,n=0时候的值

        if(y<0) cnt=0;
        else cnt=y/a+1;
        printf("%I64d\n",cnt);
    }
    return 0;
}