GCD
hi friends today I will discuss about GCD actual implementations in competitive programing .I have been facing lot of problems so here i though to make a note of the implementation of GCD.
GCD(Greatest Common Divisor) is best solved by Euclid algorithm.
gcd(a,b)=gcd(b,r) where a=bt+r;
how??
gcd(a,b)=>gcd(bt+r,b)
now bt is divisible by b,so the common division must depend on r.
code in C
faster code in C
both the codes looks different but are same as the second code uses xor, as xor has a special property of swapping the elements..(interesting application right!!)
implementation of gcd
Q)Suppose that you have two sets of people of cardinalities m,n and you want to divide them into teams of k people with every team being composed of people of only one of the original two sets.
So then what you have to do .. find the gcd of the two numbers that will be k the maximum length a team can be divided as k divides both m and n.
example
m=4,n=6
"*" and "0" represents team members in the set.
{* * * *} ,{0 0 0 0 0 0}
{* *},{* *},{0 0},{0 0},{0 0},
Q)Suppose there are two set of team of size n,m .First team consists of boys and another girls . Now on the ith day you invite (i%n)th boy and(i%m)th girl for dinner.If either of them is "happy" the other one will become "happy" and the state of happiness stays even after meeting.You are given some of the girls or boys are already in "happy" state.
So you have to find if all the boys and girls have achieved the state of happiness or not.
So brute force will be O(n*m) because there is only n*m number of pairs possible.
Now suppose this input.
n=2 m=4
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none
i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 0 1 0 1 0 1 0 (i%n)
g=0 1 2 3 0 1 2 3 0 (i%m)
^ ^ ^ ^ ^
happy states..
output :NO
Now suppose this input.
n=4 m=5
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none
i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1
g=0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
OUTPUT :YES
now O(n+m) solution
find gcd of n,m =k
and now store h[i%k]=1
then loop through 0to k if h[loop variable]=0 then NO else YES..
how??
suppose n=4 ,m=6
g= 0 1
n= 0 1
2 3
m=0 1
2 3
4 5
so if 0th and 1st position is "1" then the OUTPUT is YES else NO.
code
input file
output
YES
input file
output
YES
input file
output
NO
hi friends today I will discuss about GCD actual implementations in competitive programing .I have been facing lot of problems so here i though to make a note of the implementation of GCD.
GCD(Greatest Common Divisor) is best solved by Euclid algorithm.
gcd(a,b)=gcd(b,r) where a=bt+r;
how??
gcd(a,b)=>gcd(bt+r,b)
now bt is divisible by b,so the common division must depend on r.
code in C
1 2 3 4 5 6 7 8 9 10 11 12 13 | #include<stdio.h> int main() { int b=4,a=6;//a>b while(b) { int f=a%b; a=b; b=f; } printf("%d\n",a); return 0; } |
faster code in C
1 2 3 4 5 6 7 8 9 10 11 | #include<stdio.h> int main() { int b=10,a=25;//a>b while(b) { b^=a^=b^=a%=b; } printf("%d\n",a); return 0; } |
both the codes looks different but are same as the second code uses xor, as xor has a special property of swapping the elements..(interesting application right!!)
implementation of gcd
Q)Suppose that you have two sets of people of cardinalities m,n and you want to divide them into teams of k people with every team being composed of people of only one of the original two sets.
So then what you have to do .. find the gcd of the two numbers that will be k the maximum length a team can be divided as k divides both m and n.
example
m=4,n=6
"*" and "0" represents team members in the set.
{* * * *} ,{0 0 0 0 0 0}
{* *},{* *},{0 0},{0 0},{0 0},
Q)Suppose there are two set of team of size n,m .First team consists of boys and another girls . Now on the ith day you invite (i%n)th boy and(i%m)th girl for dinner.If either of them is "happy" the other one will become "happy" and the state of happiness stays even after meeting.You are given some of the girls or boys are already in "happy" state.
So you have to find if all the boys and girls have achieved the state of happiness or not.
So brute force will be O(n*m) because there is only n*m number of pairs possible.
Now suppose this input.
n=2 m=4
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none
i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 0 1 0 1 0 1 0 (i%n)
g=0 1 2 3 0 1 2 3 0 (i%m)
^ ^ ^ ^ ^
happy states..
output :NO
Now suppose this input.
n=4 m=5
already happy state of boys -> 1st boy(0th index)
already happy state of girls -> none
i= 0 1 2 3 4 5 6 7 8 9(assuming i(day) state from 0)
b=0 1 2 3 0 1 2 3 0 1 0 1 2 3 0 1 2 3 0 1
g=0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
OUTPUT :YES
now O(n+m) solution
find gcd of n,m =k
and now store h[i%k]=1
then loop through 0to k if h[loop variable]=0 then NO else YES..
how??
suppose n=4 ,m=6
g= 0 1
n= 0 1
2 3
m=0 1
2 3
4 5
so if 0th and 1st position is "1" then the OUTPUT is YES else NO.
code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <bits/stdc++.h> using namespace std; int gcd(int a,int b) {//a>b while(b) b^=a^=b^=a%=b; return a; } int main(int argc, char const *argv[]) { int n,m,a[1000]={0},x,x1,k; scanf("%d %d",&n,&m); k=gcd(max(n,m),min(n,m)); scanf("%d",&x); for(int i=0;i<x;i++) { scanf("%d",&x1); a[x1%k]=1; } scanf("%d",&x); for(int i=0;i<x;i++) { scanf("%d",&x1); a[x1%k]=1; } for(int j=0;j<k;j++) if(a[j]==0) { printf("NO\n"); return 0; } printf("YES\n"); return 0; } |
input file
100 50 30 50 54 7 8 59 60 61 62 63 64 15 16 18 19 20 22 73 27 79 83 86 87 89 42 93 94 45 46 97 98 20 1 2 3 5 6 17 21 24 25 26 28 30 31 32 34 35 38 40 41 49 |
output
YES
input file
2 3 0 1 0 |
output
YES
input file
2 4 1 0 1 2 |
output
NO
