Skip to main content

SPOJ - ENIGMATH solution C++

Problem Statement: ENIGMATH - PLAY WITH MATH
Heuristic: Ax - By = 0  has two possible cases:
  1.  a can divide b or if b can divide a and you can figure out the rest.
  2.  a or b cannot divide the other so it will be A B - B A = 0, but we still have to find the minimum x & y.
#include<stdio.h>
#include<math.h>
int main()
{
int t;
long long a,b;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&a,&b);
if(a%b==0||b%a==0)
{
if(a>b) printf("1 %lld\n",a/b);
else if(a<b) printf("%lld 1\n",b/a );
else printf("1 1\n");
}
else
{
while(a%2==0&&b%2==0)
{
a=a/2;
b=b/2;
}
int lim=(a<b)? sqrt(a):sqrt(b);
for(int i=3;i<=lim;i+=2)
{
while(a%i==0&&b%i==0)
{
a=a/i;
b=b/i;
}
}
printf("%lld %lld\n",b,a);
}
}
}
view raw enigmath.cpp hosted with ❤ by GitHub



Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...
14 comments
Read more

Trailing Zeroes of n!

Find the number of trailing zeroes in 122! ?  That's a big number right? The solution is pretty simple. Ask yourself when does any multiplication results in a trailing zero? The answer is (2x5) = 10, leaves one zero behind. The factorial of 122 is a multiplication which you already know. The expansion is, 98750442008336013624115798714482080125644041369 78359605958470050267671457205014364903379642774 50422940710230505796264047365129395968426948958 2137821062001338805474721479524352 0000000000000 000000000000000 So, we have to find the number of multiples of 5 from the expansion and they are 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120. So there are 24 multiples of 5. then again, 25= 5 x 5 , which has another extra factor of  5 to count. So how many multiples of 25 from 1 to 122? (122 / 25) = 4 (taking the only integer) So, add that 4 to the earlier count. 24 + 4 = 28 , so we have 28 trailing zero in 122! Let's take a num...
Post a Comment
Read more

Minimum moves for balancing brackets

You’re given a non-empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition of being stable is as follows: An empty string is stable. If S is stable, then {S} is also stable. If S and T are both stable, then ST (the concatenation of the two) is also stable. All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{. The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa. Solution Heuristics: Traverse the string. When the number of opening braces( { ) matches the number of closing braces ( } ), the string is balanced. Else it's not balanced. So count both of them. Make a list. Insert only opening braces. If a closing brace is found delete one brace( if the size of the list is > 0 ) from the list. Because they would make a pair. If the list is empty then we'll conve...
Post a Comment
Read more