[BOJ] 1490 자리수로 나누기

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

1490번: 자리수로 나누기

알고리즘: Math (최소공배수-소인수분해)

 

 

접근:

1. N의 0이 아닌 모든 자리수로 나누어 떨어져야 함. -> 각 자리수들의 최소공배수

$$Ans = lcm(a_0, a_1, ... , a_k)*t$$

2. N으로 시작하면서 ...

$$N*10^k \le Ans < N*10^{(k+1)}$$

$$let\ m=lcm(a_0, a_1, ... , a_k)$$

$$Then, {N*10^k\over m}\le t$$

$$\therefore\ t=\lceil {N*10^k\over m}\rceil$$

 

이제, 2번 조건을 만족하는 정수 t가 존재할 때까지 k를 증가시키면서 확인해주면 된다.

(최소공배수 구하는 부분은 어차피 수가 0~9까지 밖에 없으므로 미리 DB 테이블을 작성해서 구함)

 

#include<iostream>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
typedef long long int llt;

llt N, t, p;
bool chk[10];
int c[10][4] = {{0, }, {0, }, {1,0,0,0}, {0,1,0,0}, {2,0,0,0}, {0,0,1,0}, {1,1,0,0}, {0,0,0,1}, {3,0,0,0}, {0,2,0,0}};
int n[4], m, v[4] = {2, 3, 5, 7};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	
	for(llt i = N; i > 0; i /= 10)
	{
		for (int j = 0; j < 10; j++)
		{
			n[j] = MAX(n[j], c[i%10][j]);
		}
	}

	m = 1;
	for (int i = 0; i < 4; i++)
	{
		if (n[i])
		{
			for (int j = 0; j < n[i]; j++)
				m *= v[i];
		}
	}
	p = 1;
	while (1)
	{
		t = N * p / m;
	//	cout << t << "	" << m * t / p << "  " << m * (t+1) / p << endl;
		if (m * t / p == N)
		{
			cout << m * t;
			break;
		}
		else if (m * (t+1) / p == N)
		{
			cout << m * (t+1);
			break;
		}
		p *= 10;
	}
	return 0;
}