GCD

What does this have to do with C++?

Yet another codechef problem. YACCP.

jonnin (11429)

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

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;
}

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

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.

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

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

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).

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.

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

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.

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';
            }
        }
}

Last edited on

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;
}

okfree (4)

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

@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?