백준 3955번 캔디분배

<백준 3955번 캔디분배 - 마포 코딩박>

사용한 알고리즘: 수학 ( Extended Euclidean Algorithm )


문제에서는 K 와 C 를 준 후, Cx = 1 (mod K) 를 만들 수 있는 x 를 구하는 문제였습니다.

사실 이 문제는 Extended Euclidean Algorithm 을 알아야 풀 수 있는 문제였습니다.
간단히 설명하자면, ax+by = gcd(a,b) 를 풀이하는 diopantine 방정식을 구현한 후, 이때 gcd(a,b) = 1 이라고 한다면, 이는 ax + by = 1 꼴이 되고,
이를 통해 문제에 적용하면, ax + by = Cx + M = Cx = 1 (mod M) 꼴이 됩니다.
다시말해 C와 M의 gcd가 1이 아니면 Cx = 1 (mod M) 꼴을 만족하는 x 를 찾을 수 없습니다.

구현 자체는 어렵지 않은 수학 문제였습니다.
참고로 사탕을 모든 M 명에게 나눠주고 싶기 때문에 Cx > M 이어야 합니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define pii pair<int, int>
	int T, K, C;
	int GCD(int x, int y){
	if(y==0) return x;
	else return GCD(y, x%y);
	return 0;
	}
	// ax+by=gcd(a,b) 가 되는 x, y 를 구함
	pii ext_gcd(int a,int b){
	if(b){
	pii tmp = ext_gcd(b, a%b);
	return pii(tmp.second, tmp.first - (a/b) * tmp.second);
	} else return pii(1, 0);
	}
	// ax = 1 (mod M) 을 만족하는 x 구함, gcd(x,M)=1 일때만 해가 있다.
	ll mod_inv(int a, int M){
	return (ext_gcd(a, M).first + M) % M;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin>>T;
	while(T--){
	cin >> K >> C;
	if(GCD(C,K)!=1){
	cout << "IMPOSSIBLE" << '\n';
	continue;
	}
	// Cx = 1 (mod K) 를 구하는 문제이지만 사탕을 K명에게 나누어주려면 Cx > K 이어야 하겠죠.
	ll ans = mod_inv(C,K);
	while(C*ans<=K) ans+=K;
	if(ans>1e9) cout << "IMPOSSIBLE" << '\n';
	else cout << ans << '\n';
	}
	return 0;
	}

view raw BOJ 3955.cpp hosted with ❤ by GitHub