백준 1565 수학

문제링크

https://www.acmicpc.net/problem/1565

문제

풀이

D에 있는 모든 수의 배수 이면서 M에 있는 모든 수의 약수인 수를 구하면 되므로 먼저 D의 최소공배수와 M의 최대공약수를 구해주었다.

최대공약수의 모든 약수는 M에 있는 모든 수의 약수가 되므로 결국 M의 최대공약수의 약수인 수 중에서 D의 최소공배수의 배수인 수를 찾는 문제이다.

약수 구하기 알고리즘을 통해 각 약수가 lcm(최소공배수)로 나누어 떨어지면 cnt++ 를 시키며 값을 구해주었다.

시행착오

약수 구하기 알고리즘에서 코딩적인 실수가 있어 93% 에서 여러번 틀렸다.
(오버플로우 문제인줄 알고 이상한곳만 손 보다가 계속틀렸다 !)

코드

#include <iostream>
using namespace std;
typedef long long ll;
ll D[51], M[51];
ll vlcm, vgcd;
ll gcd(ll a, ll b) {
	while (b != 0) {
		ll r = a % b;
		a = b;
		b = r;
	}
	return a;
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int d, m;
	cin >> d >> m;
	for (int i = 0; i < d; i++) cin >> D[i];
	for (int i = 0; i < m; i++) cin >> M[i];

	vgcd = M[0];//최대공약수
	for (int i = 1; i < m; i++) vgcd = gcd(vgcd, M[i]);

	vlcm = 1;//최소공배수
	for (int i = 0; i < d; i++) {
		vlcm = lcm(vlcm, D[i]);
		if (vlcm > vgcd || vlcm == 0) {
			cout << 0;
			return 0;
		}
	}

	ll i, cnt = 0;
	for (i = 1; i*i < vgcd; i++) {
		if (vgcd%i == 0) {
			if (i%vlcm == 0) cnt++;
			if ((vgcd / i) % vlcm == 0) cnt++;
		}
	}
	if (i*i == vgcd && (i%vlcm == 0)) cnt++;
	cout << cnt;
}

후기

참고할만한 링크

https://m.blog.naver.com/PostView.nhn?blogId=soohan530&logNo=221029295310&proxyReferer=https:%2F%2Fwww.google.com%2F
약수 구하기 알고리즘

https://m.blog.naver.com/PostView.nhn?blogId=writer0713&logNo=221133124302&proxyReferer=https:%2F%2Fwww.google.com%2F
최대공약수 최소공배수 알고리즘