TIOJ 1098 A.好多油瓶

[數學]
先搜到 ap+bq=n的其中一組解(a0,b0)，再往上或下搜，一轉折就停止。
複雜度O(N)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<ctype.h>

int gcd(int a,int b)
{
    if(a<b){int tmp=a;a=b;b=tmp;}
    if(a%b==0)
        return b;
    return gcd(b,a%b);
}
bool findlinear(int p,int q,int n,int *a,int *b)
{
    if(n%gcd(p,q)!=0)
        return false;
    //pa+qb=n
    for(int lx=0;lx<p;lx++) //run on b
    {
        if((n-lx*q)%p==0)
        {
            *a=(n-lx*q)/p;
            *b=lx;
            return true;
        }
    }
}
int cost(int a,int b)
{
    if(a*b==0)
    {
        if(a==0)
            return 2*b;
        else
            return 2*a;
    }
    if((a>0)&&(b>0))
        return 2*(a+b);
    return (2*(abs(a)+abs(b))-1);
}
int main()
{
    int p,q,n;
    int a,b;
    while((scanf("%d %d %d",&p,&q,&n)==3))
    {
        if((!p)&&(!q)&&(!n)) break;
        if(findlinear(p,q,n,&a,&b)==false)
        {
            printf("No\n");
            continue;
        }
        int g=gcd(p,q);
        p/=g;q/=g;n/=g;
        findlinear(p,q,n,&a,&b);
        //printf("(%d,%d)\n",a,b);
        int cost0=cost(a,b);
        int costprc1=cost0,costprc2=cost0;
        int pa,pb;
        for(pa=a,pb=b;costprc1>=cost(pa,pb);pa-=q,pb+=p)
        {
            costprc1=cost(pa,pb);
            //printf("[%d,%d]%d\n",pa,pb,cost(pa,pb));
        }

        for(pa=a,pb=b;costprc2>=cost(pa,pb);pa+=q,pb-=p)
        {
            costprc2=cost(pa,pb);
            //printf("{%d,%d}%d\n",pa,pb,cost(pa,pb));
        }

        if(costprc1>costprc2)
            printf("%d\n",costprc2);
        else
            printf("%d\n",costprc1);
    }
    return 0;
}