9267 문제 풀이 기록

(A,B)로부터 a+=b, b+=a 를 통해 만들어진 수를 (iA+uB, jA+vB) 라고 설정하면

이들의 합 (i+j)A + (u+v)B는 A, B 정수 계수를 갖는 선형결합이므로

배주 항등식에 의해 (i+j)A + (u+v)B = gcd(A,B)가 된다

 

배주 항등식
0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면, 수식을 만족하는 해 (x,y)는 반드시 존재한다
$ax+by=d$
특히 a와 b가 서로소이고 d=1이라면, 베주의 항등식에 의해 정수해가 반드시 존재한다
확장 유클리드 수식과 완전히 동일하지만, 여기서는 (x,y) 해가 반드시 존재함에 포커싱을 둔다

 

여기까진 질문탭에 있는 답변이었다. 다르게 생각해 볼까

처음 시작하는 a, b값을 각각 a0 b0이라고 하면, 두 명령을 적용해서 만들 수 있는 수는 모두 a0x+b0y (x>0, y>0) 꼴이다

그리고 a0, b0으로 시작해서 만들 수 있는 수는 모두 처음에 a0+b0, b0 또는 a0, a0+b0 으로 시작해서 만들 수 있는 수이다

만약 a0, b0에서 시작해서 4a0+10b0을 만들 수 있다면,

4a0+10b0=4(a0+b0)+6b0 이므로,

a0+b0, b0에서 시작해서 4(a0+b0)+6b0 을 만들 수 있다는 의미이고,

이는 a0+b0, b0에서 시작해서 4a0+6b0 = 4(a0+b0)+2b0 을 만들 수 있다는 의미이고,

이는 a0+b0, b0에서 시작해서 4a0+2b0 = 2a0+2(a0+b0) 을 만들 수 있다는 의미이고,

이는 a0, a0+b0에서 시작해서 2a0+2b0 = 2(a0+b0)을 만들 수 있다는 의미이고,

2a0 또는 2b0을 만들 수 있는데 이건 불가능하므로 4a0+10b0은 불가능하다

 

어쨌든 a0x+b0y 를 만들 수 있다면 위 과정을 통해 gcd(x,y)a0 이나 gcd(x,y)b0 또한 만들 수 있어야 하므로 gcd(x,y)=1이어야 한다

 

따라서 이 문제는 확장 유클리드 알고리즘으로 Ax+By =gcd(A,B) 의 첫 해 a0, b0을 찾은 다음, 일반해들을 순회하면서 다음 조건이 성립하는 정수 x,y가 존재하는지 확인하여 해결한다

a0x+b0y = s

gcd(x,y)=1

x>0, y>0

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <memory.h>
using namespace std;
struct INFO {
	long long gcd, s, t;
};
INFO euc(long long a, long long b) { //확장 유클리드
	if (b == 0) {
		INFO res = { a,1,0 };
		return res;
	}
	INFO res = euc(b, a % b);
	INFO resres = { res.gcd, res.t, res.s - (a / b) * res.t };
	return resres;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long a, b, s;
	cin >> a >> b >> s;

	if (a == 0 && b == 0) {
		cout << "NO"; return 0;
	}
	if (a == 0) {
		if (s % b == 0) cout << "YES";
		else cout << "NO";
		return 0;
	}
	if (b == 0) {
		if (s % a == 0) cout << "YES";
		else cout << "NO";
		return 0;
	}
	INFO num = euc(a, b);
	if (s % num.gcd != 0) {
		cout << "NO"; //안 나눠지면 그냥 끝
		return 0;
	}
	cout << "enu res: " << num.gcd << " " << num.s << " " << num.t;
	//여기까진 잘 나옴
    
	long long g = num.gcd;
	long long x = num.s * (s / g); //a0
	long long y = num.t * (s / g); //b0
	//cout << x << " " << y;	
	
	for (int i = -g * (x / (b + 1)); i <= g * (y / (a + 1)); i++) {
		if (euc(x + (i * b / g), y - (i * a / g)).gcd == 1) {
			cout << "YES"; return 0;
		}
		else {
			cout << "NO"; return 0;
		}
	}
}

이렇게 하면 17%까진 긁는다(의미없음ㅋㅋ)

좀 더 이해가 필요함.. 일단 여기까지 기록