이것이 가능합니까? 마지막 몇 자리 합계가 다른 숫자

Question

나는 임의의 숫자를 여러 번 사용할 수있는 n 자리 숫자와 숫자 목록이 있습니다.

목록의 번호를 사용하면 합계의 마지막 n 자릿수가 n 자릿수가되도록 합계를 생성 할 수 있다는 것을 어떻게 알 수 있습니까?

참고 : 합계에는 0이 아닌 초기 값이 있습니다.

EDIT - 해결책이있는 경우 추가 된 숫자의 최소 수를 찾아서 주어진 숫자로 마지막 4 자리 숫자를 얻으십시오. DP (최소 동전 변경 문제)로 쉽게 해결할 수 있습니다.

예를 들어, 그것은 쉽게

Given number = 1212 
Initial value = 5234 
List = [1023, 101, 1] 
A solution exists: 21212 = 5234 + 1023*15 + 101*6 + 1*27 

Answer 1

N = 4, 반례를 찾는 경우 (주석 참조).

이제 용액 여기 동적 프로그래밍 접근법 :

모든 산술은 모듈로 10^N이다. 0 - 10^n-1 범위의 각 값에 대해 플래그가 필요하고 처리 할 요소의 대기열이 필요합니다.

1. 처리 목록에 초기 값을 푸시합니다.
2. 처리 대상 목록에서 요소를 가져옵니다. 비어 있으면 완료됩니다. 해결책 없음.
3. 각 번호를이 번호에 개별적으로 추가하십시오. 이미 발견 되었다면 할 일이 없습니다. 합계를 찾으면 끝났습니다. 해결책이 있습니다. 그렇지 않은 경우 발견 된 것으로 표시하고 대기열로 밀어 넣으십시오.
4. 고토 당신이 수에 도달하는 방법을 저장하는 경우 실제의 솔루션을 재구성 할 수있는 2

. 초기 값에 도달 할 때까지 합계에서 뒤로 돌아 가야합니다.

Answer 2

목록에있는 숫자의 가장 일반적인 요소가 1ⁿ (즉, 2 또는 5로 나눌 수 없음) 모듈 모듈 인 경우 다른 주어진 값의 선택에 대한 문제를 해결할 수 있습니다. 확장 된 유클리드의 알고리즘을 사용하여 gcf에 합한 목록의 선형 조합을 찾고 gcf 모듈로 ​​1ⁿ의 곱셈 역함수를 찾고 주어진 값과 초기 값의 차이를 곱합니다.

목록의 숫자 gcf가 2 또는 5로 나눌 수있는 경우 (즉, 단위가 아님) 주어진 값과 초기 값의 차이가 2 또는 5로 나눌 수있는 경우에는 목록 및 2와 5의 가장 큰 힘에 의한 차이를 모두 나눌 수 있습니다. 당신이 끝내는 gcf가 단위 인 경우에 해결책이 있고 당신은 위 절차에 그것을 찾아 낼 수있다. 그렇지 않으면 해결책이 없습니다.

예를 들어 합계가 16이고 초기 값이 5이고 숫자 목록이 [3]입니다.

목록에있는 숫자의 gcf는 3 단위입니다. 그것의 역 모듈로 100은 67입니다 (3 × 67 = 201).

주어진 숫자와 초기 값의 차이에 16-5 = 11을 곱하면 3에 대해 67 * 11 = 737이됩니다.우리는 modulo 100에서 37와 같기 때문에 작동합니다.

결과를 확인하십시오 : 5 + 37 × 3 = 16. 예, 작동합니다.