Archive for the ‘GCD/LCM’ Category

UVA – 10368 – Euclid’s Game   Leave a comment


two players alternate turns on this game:given two numbers a,b you can subtract a multiple of the smaller number from the bigger one, the first player who gets a zero on either number wins.

Its easy to notice that a game with even number of turns means that the second player wins, other wise the first player wins.

assume number of turns is nTurns
so at any game state a player may try to make nTurns%2==1 or nTurns%2==0, so how do we control the number of turns?

let the two numbers of the game state a,b where a>=b
if we want to leave the number of turns as it is then the next game state should be b,a%b, otherwise the next game state may be b+a%b,b so the next player will waste a turn to go to the state b,a%b
this is not always applicable except if a/b > 1 as if a/b = 1 thus we can’t increase number of turns by 1 (i.e we can’t skip a turn)

you should notice that the effect of other multiples is really useless as for example if 2b + a%b,b
or 3b + a%b,b those are really the same as b,a%b and b+a%b,b…

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class EcluidsGame {
	public static int winner(int p, int a, int b) {
		if (b == 0)
			return p ^ 1;
		int win = p ^ 1;
		if (winner(p ^ 1, b, a % b) == p)
			win = p;
		if (a / b != 1 && winner(p ^ 1, b + (a % b), b) == p)
			win = p;
		return win;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		String[] win = { "Stan wins", "Ollie wins" };
		while (true) {
			int a = in.nextInt();
			int b = in.nextInt();
			if (a == 0 && b == 0)
				break;
			System.out.println(win[winner(0, Math.max(a, b), Math.min(a, b))]);
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 27, 2012 by epicrado in GCD/LCM, Mathematics

UVA – 408 – Uniform Generator   Leave a comment


seed(i+1) = (seed(i)+step)%mod
let seed(0) = 0
then we want to prove that
{0*step,1*step,2*step,….,(mod-1)*step} is a permutation of {1,2,3,4,5,6…,mod-1}
This is correct iff gcd(step,mod)=1 i.e they don’t share any prime factors
Proof:
lets start with
A = {1,2,3,4,5,6…,mod-1} multiply by n
X = {1*n,2*n,3*n,…(mod-1)*n}
to prove that X is a permutation of A lets assume A[i]*n = A[j]*n (mod mod) for some i and j
since n is relatively prime to mod then we can cancel it from both sides
then A[i]=A[j] (mod mod) which is only true if i = j
then X is a permutation of A

#include <stdio.h>
int gcd(int a,int b)
{
	return (b==0)?a:gcd(b,a%b);
}
int main()
{
	int a,b;
	while(scanf("%d %d",&a,&b)==2)
		printf("%10d%10d    %s Choice\n\n",a,b,(gcd(a,b)==1)?"Good":"Bad");
	return 0;
}

Posted February 14, 2012 by epicrado in GCD/LCM

UVA – 10407 – Simple division   1 comment


Problem:given an list of integers A with length n.find a number M such that for all integers in A, A[i]%M is the same.
Starting from the problem statement
we want
A[0]=aM + r
A[1]=bM + r
A[2]=cM + r
etc..
then for any 2 integers i,j A[i]-A[j] is a multiple of M
then M = GCD(A[i]-A[j]) for all i,j < n

#include <stdio.h>
int abs(int a)
{
	return (a>=0)?a:-a;
}
int gcd(int a,int b)
{
	return (b==0)?a:gcd(b,a%b);
}
int main()
{
	int inp[1001],i,j,n,g;
	while(1)
	{
		scanf("%d",inp);
		if(inp[0]==0)
			break;
		int top = 1;
		while(scanf("%d",inp+top)&&inp[top]!=0)
			top++;
		g = 0;
		for(i=0;i<top;i++)
			for(j=i+1;j<top;j++)
				if(inp[i]-inp[j]!=0)
					g = gcd(abs(inp[i]-inp[j]),g);
		printf("%d\n",g);		
		
	}	
	return 0;
}

Posted February 9, 2012 by epicrado in GCD/LCM

UVA – 10622 – Perfect P-th Powers   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class PerfectPthPowers {
	public static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		boolean[] isPrime = new boolean[1 << 16];
		isPrime[0] = isPrime[1] = true;
		for (int i = 2; i * i < isPrime.length; i++)
			if (!isPrime[i])
				for (int j = i * i; j < isPrime.length; j += i)
					isPrime[j] = true;
		LinkedList<Integer> res = new LinkedList<Integer>();
		for (int i = 2; i < isPrime.length; i++)
			if (!isPrime[i])
				res.add(i);
		while (true) {
			long t = Long.parseLong(in.readLine());
			if (t == 0)
				break;
			long sign = t / Math.abs(t);

			t = Math.abs(t);

			int g = 0;
			for (int i : res) {
				if (t % i == 0) {
					int c = 0;
					while (t % i == 0) {
						t /= i;
						c++;
					}
					g = gcd(c, g);
				}
				if (t == 1)
					break;
			}
			if (t != 1)
				g = gcd(1, g);
			while (sign < 0 && g % 2 == 0)
				g /= 2;
			System.out.println(g);
		}
	}
}

Posted February 6, 2012 by epicrado in GCD/LCM, Mathematics, Prime numbers

UVA – 11889 – Benefit   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Benefit {
	public static void main(String[] args) throws NumberFormatException,
			IOException {
		int[] pfactor = new int[10000001];
		pfactor[0] = pfactor[1] = -1;
		for (int i = 2; i * i < pfactor.length; i++)
			if (pfactor[i] == 0)
				for (int j = i * i; j < pfactor.length; j += i)
					pfactor[j] = i;
		for (int i = 2; i < pfactor.length; i++)
			if (pfactor[i] == 0)
				pfactor[i] = i;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(in.readLine());
		while (t-- > 0) {
			TreeSet<Integer> S = new TreeSet<Integer>();
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int temp = a;
			while (pfactor[temp] != -1) {
				S.add(pfactor[temp]);
				temp /= pfactor[temp];
			}
			boolean good = true;
			int res = c;
			for (int i : S) {
				int r1 = 1;
				int r2 = 1;
				int t1 = a;
				int t2 = c;
				while (t1 % i == 0) {
					t1 /= i;
					r1 *= i;
				}
				while (t2 % i == 0) {
					t2 /= i;
					r2 *= i;
				}
				if (r1 > r2) {
					good = false;
					break;
				}
				if (r1 == r2)
					res /= r1;
			}
			if (good)
				System.out.println(res);
			else
				System.out.println("NO SOLUTION");
		}
	}
}

Posted February 6, 2012 by epicrado in GCD/LCM, Mathematics, Prime numbers

UVA – 10717 – Mint   Leave a comment


Hint
Simple observations
Length of a table leg must be a multiple of coin thickness i.e length % coinThickness = 0
Length of all table legs must be equals
We need only four coinTypes to make a table (c1,c2,c3,c4)
Solution
since length%c1=0,length%c2=0,length%c3=0,length%c4=0
then length must be a multiple of LCM(c1,c2,c3,c4)

import java.util.Scanner;

public class Mint {
	public static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	public static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[] coins = new int[51];
		int nC = in.nextInt();
		int nT = in.nextInt();
		while (nC != 0 || nT != 0) {
			for (int i = 0; i < nC; i++)
				coins[i] = in.nextInt();
			for (int i = 0; i < nT; i++) {
				int t = in.nextInt();
				int max = Integer.MIN_VALUE;
				int min = Integer.MAX_VALUE;
				for (int a = 0; a < nC; a++)
					for (int b = a + 1; b < nC; b++)
						for (int c = b + 1; c < nC; c++)
							for (int d = c + 1; d < nC; d++) {
								int len = lcm(lcm(coins[a], coins[b]),
										lcm(coins[c], coins[d]));
								max = Math.max(max, (t / len) * len);
								min = Math.min(min,
										(t / len + ((t % len != 0) ? 1 : 0))
												* len);

							}
				System.out.println(max + " " + min);
			}
			nC = in.nextInt();
			nT = in.nextInt();
		}
	}
}

Posted December 28, 2011 by epicrado in GCD/LCM

UVA – 10680 – LCM   Leave a comment


#include <stdio.h>
#include <math.h>
#define N 1000001
char primes[N];
int prime[78497];
int multi[N];
int dp[N];
int modPow(int b,int e,int m)
{
	int res = 1;
	while(e)
	{
		if(e&1)
			res = (res * b)%m;
		e>>=1;
		b = (b*b)%m;
	}
	return res;
}
int main()
{
	int top = 0;
	double d;
	int i,j,t,f;
	for( i = 0;i<N;i++)
	{
		primes[i]=1;
		multi[i]=1;
	}
	primes[0]=primes[1]=0;
	for( i  = 2;i*i<N;i++)
		if(primes[i])
			for( j=i*i;j<N;j+=i)
				primes[j]=0;
	prime[top++]=3;
	for( i=7;i<N;i++)
		if(primes[i])
			prime[top++]=i;
	for(i=0;prime[i]<1000;i++)
		for(j=prime[i];j<N;j*=prime[i])
			multi[j]=prime[i];
	for(;i<top;i++)
		multi[prime[i]]=prime[i];
	dp[1]=1;
	for( i = 2;i<N;i++)
		dp[i] = (multi[i]*dp[i-1])%10;
	int n;
	scanf("%d",&n);
	while(n)
	{
		d = log(n);
		t = d/log(2);
		f = d/log(5);
		dp[n]=(dp[n]*(modPow(2,t-f,10)))%10;
		putchar('0'+dp[n]);
		putchar('\n');
		scanf("%d",&n);
	}
	return 0;
}

Posted September 23, 2011 by epicrado in GCD/LCM, Prime numbers