백준 1565 수학

jathazp·2021년 4월 16일

수학 알고리즘 최대공약수 최소공배수

algorithm

목록 보기

23/57

문제링크

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
최대공약수 최소공배수 알고리즘

jathazp

이전 포스트

백준 14391

다음 포스트

백준 1071 소트

2개의 댓글

한규원

2022년 7월 17일

전 왜자꾸 틀렸다고나오는지 한번만 봐주실수있나요.. ㅜㅜ

#include <stdio.h>
long long int GB(long long int a,long long int b);//최소공배수
long long int GY(long long int a,long long int b);//최소공약수

int main()
{
    long long int D[51]={0,};
    long long int M[51]={0,};

    int number_d,number_m;

    scanf("%d",&number_d);
    scanf("%d",&number_m);

    for(int i=0;i<number_d;i++)
    {
        scanf("%d",&D[i]);
    }

    for(int i=0;i<number_m;i++)
    {
        scanf("%d",&M[i]);
    }

    long long int gongbae=1;
    for(int i=0;i<number_d;i++)
    {
        gongbae=GB(gongbae,D[i]);
    }


    long long int gongyak=M[0];
    for(int i=1;i<number_m;i++)
    {
        gongyak=GY(gongyak,M[i]);
        if(gongyak>gongbae||gongyak==0)
        {
            printf("0");
            return 0;
        }
    }


    long long int save_count=0;
    long long int i;
    for(i=1;i*i<gongyak;i++)
    {
        if(gongyak%i==0)
        {
            if(i%gongbae==0) save_count++;
            if((gongyak/i)%gongyak==0) save_count++;
        }
    }

    if(i*i==gongyak&&(i%gongbae==0))save_count++;

    printf("%d",save_count);
}

long long  int GB(long long int num1,long long int num2) // 최소 공배수 함수
{
    return (num1*num2)/GY(num1,num2);
}

long long int GY(long long int num1,long long int num2)
{
    while(num2!=0)
    {
        long long int temp=num1%num2;
        num1=num2;
        num2=temp;
    }
    return num1;
}

1개의 답글