GCD

What does this have to do with C++?

Aug 9, 2018 at 4:01pm

Yet another codechef problem. YACCP.

Aug 9, 2018 at 4:28pm

jonnin (11490)

At least its exposing people to some math. When they do it on their own, that is.
Hacker, read the other threads. I think your approach is correct, but to be blunt in a friendly way, I don't care enough to sit down with the math to validate it for you. I did my time in college doing wonky proofs in senior math classes, and got my fill of it for life there. You can either prove it on paper or test it to death to see if it works, or submit it and see if it spits back the wrong answer code. I would just do that... best as I can tell you get full points if it gives the right answer, even if the code is not generally correct...

Last edited on Aug 9, 2018 at 4:30pm

Aug 9, 2018 at 6:17pm

I gave this a try. Let me know what you think...

#include <iostream>
#include <vector>
using namespace std;

int power(int base, unsigned p) {
	int x = base;
	for (int i = p; i > 1; i--) {
		base *= x;
	}
	return base;
}

int gcd(int x, int y) {
	vector<int> first;
	vector<int> second;
	for (int i = 1; i <= abs(x / 2); i++) {
		if (x % i == 0) {
			first.push_back(i);
		}
	}
	first.push_back(abs(x));
	for (int i = 1; i <= abs(y / 2); i++) {
		if (y % i == 0) {
			second.push_back(i);
		}
	}
	second.push_back(abs(y));
	for (int i = first.size() - 1; i >= 0; i--) {
		for (int j = second.size() - 1; j >= 0; j--) {
			if (first[i] == second[j]) {
				return first[i];
			}
		}
	}

	return 0;
}

int main()
{
	int a = 10;
	int b = 20;
	int n = 3;

	//cout << power(a, n) << "\n";
	//cout << power(b, n) << "\n";
	cout << gcd(power(a, n) + power(b,n), a - b);

	cin.get();
	return 0;
}

Edit & Run

Aug 9, 2018 at 6:40pm

The exponent may be as high as a billion. I think you have an overflow problem.

Aug 9, 2018 at 7:21pm

My logic is that gcd(a^n+b^n,a-b)=gcd(a+b,a-b) for every test case this is working

For every test case?
What about a=1, b=2, n=2: 1^2 + 2^2 = 5, but 5 is not divisible by 1 + 2.

Aug 9, 2018 at 7:58pm

Umm yeah. Don't put a billion in please.

Aug 9, 2018 at 9:40pm

What about a=1, b=2, n=2: 1^2 + 2^2 = 5, but 5 is not divisible by 1 + 2.

GCD(5, -1) = 1
GCD(3, -1) = 1

Aug 9, 2018 at 10:15pm

Really? But he said it was because a^n + b^n = (a+b)(...). That's actually what I thought was wrong. I didn't think farther to check gcd with a - b, but when I do it does seems that gcd(a^n+b^n, a-b) = gcd(a+b, a-b).

Aug 9, 2018 at 11:03pm

I think what they meant was that (a+b)^n = a^n + b^n + (etc), which yes, is quite a weaker statement.
I don't really know how to go about proving that GCD(a^n+b^n, a-b) = GCD(a+b, a-b). Raising the terms of a sum has no consistent pattern on the prime factors.

Aug 10, 2018 at 12:36am

Raising the terms of a sum has no consistent pattern on the prime factors.

I guess that's what makes it interesting.

But I seem to have found a counter example:

GCD(10^2 + 2^2, 10 - 2) = GCD(104, 8) = 8      (104 / 8 = 13)
GCD(10   + 2  , 10 - 2) = GCD( 12, 8) = 4

Same kind of thing when cubed (or any greater exponent):

GCD(10^3 + 2^3, 10 - 2) = GCD(1008, 8) = 8     (1008 / 8 = 126)
GCD(10   + 2  , 10 - 2) = GCD(  12, 8) = 4

But perhaps a solution could still be based on GCD(a+b, a-b) with some kind of adjustment.

Last edited on Aug 10, 2018 at 12:41am

Aug 10, 2018 at 12:50am

Huh. That's interesting. 10^n + 2^n is divisible by 2^(n+1), at least up to n=10. And the power for 3 goes 1, 0, 2, 0, 1, 0, 1, 0, 3, 0. Weird.

Aug 10, 2018 at 1:06am

A pattern for some values that form counter examples (x an int >= 0):

   a         b
10 +  8x     2
12 +  9x     3
20 + 16x     4
30 + 25x     5

b=6 is more complicated (presumably because 6 is 2 * 3):

   a         b
14 +  8x     6
15 +  9x     6

Program used to generate the data (displays absolute values of what I'm calling "b" first, then a, then GCD(a^2+b^2,a-b) then GCD(a+b,a-b)):

#include <iostream>
#include <iomanip>

long gcd(long a, long b) {
    if (b == 0) return 1;  // GCD(X, 0) = 1
    while (b != 0) { long t = b; b = a % b; a = t; }
    return a;
}

void o(long x) {std::cout << std::setw(4) << std::abs(x) << ' ';}

int main() {
    for (long a = 1; a < 100; a++)
        for (long b = a; b < 100; b++) {
            long g1 = gcd(a*a + b*b, a - b);
            long g2 = gcd(a + b, a - b);
            if (std::abs(g1) != std::abs(g2)) {
                o(a);o(b);o(g1);o(g2);std::cout<<'\n';
            }
        }
}

Edit & Run

Last edited on Aug 10, 2018 at 1:08am

Aug 10, 2018 at 1:31pm

For some reason google says this works, and it seems to...

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long gcd(long long x, long long y) {
	long long temp;
	while (y != 0) {
		temp = y;
		y = x % y;
		x = temp;
	}
	return abs(x);
}


int main()
{
	
	long long a, b, n;
	
	cout << "Enter a, b, and n values: ";
	cin >> a >> b >> n;

	
	cout << gcd(pow(a, n) + pow(b,n), a - b);

	cin.ignore();
	cin.get();
	return 0;
}

Edit & Run

Aug 10, 2018 at 1:54pm

okfree (4)

Why won't that work? It's the same GCD algorithm

Aug 10, 2018 at 2:06pm

@manga, You are totally missing the point. Try a=3000, b=300, n=1000000000.

For me your program prints 4 but the answer would obviously contain a factor of 3.

Hint: What does pow(a, n) print?

Aug 10, 2018 at 2:23pm