Greatest Dumpling Fight :: On a solving Spree ...

From this week on we start solving problems on Codechef, Interviewstreet etc. . with the view to improve your problem solving skills ..
          Apart from the code we will give a detailed mathematical and logical explanation about the problem.So lets start with something easy ..

LINK :: Question 1

Required Concepts : Euclid Algorithm

Well for both chefs we have A,B and C,D units that they can go .. so any length that is traversable by first chef is a multiple of gcd(A,B) and similarly any length that is traversable by second chef is a multiple of gcd(C,D) .. Hence units which are traversable by both are multiples of lcm=LCM(gcd(A,B),gcd(C,D)).Thus for the positive half of 1 to K number of such units equals K/lcm which is same on the other side of the rope. Hence our answer is 2*(K/lcm) + 1(bcz 0 is traversable by both as both can go forward and come back by same value).

typedef unsigned long long LL;
int T;
LL A,B,C,D,K;

LL gcd(LL a,LL b)    //euclid method for fast gcd
{
    if(b>a)
    return gcd(b,a);
    else
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>A>>B>>C>>D>>K;
        LL n1=gcd(A,B);
        LL n2=gcd(C,D);
        LL den=gcd(n1,n2);
        LL S=n1/den;     //split the LCM part 1
        LL R=K/S;        //LCM part 2
        LL n4=R/n2;      //the final value
        cout<<(2*n4)+1<<endl;
    }
    return 0;
}

For finding LCM of a and b we used (a*b/gcd(a,b)) ..