피보나치 수열이란게 있는데요.
다음과 같은 수열 입니다.

1 1 2 3 5 8 13 21 34 .....

이전 두항이 합이 다음 항으로 나오는 수열입니다.

이 수열의 일자리 수만 취하여 한 숫자를 만듭니다.

112358314 ....

이 수를 180만 자리까지 만들었을 때 이 수는 어떤 수 X의 배수가 될 것입니다.
최소의 X는 무엇ㅇ르까요? 단 X는 2와 5 는 아니라고 제한합니다.

답은 밑에...









































































수열을 적어보다 보면 60자리 마디로 순화함을 알 수 있습니다.

11235 83145 94370 77415 61785 38190 99875 27965 16730 33695 49325 72910 11235... (다시 반복.. )

112 358 314 594 370 774 156 178 538 190 998 752 796 516 730 336 954 932 572 910 = A로 치환하면

A X ( ...100...00100....00100....001 ) -> 괄호안에서 1과 1사이에는 0이 60개
= A X ( 1 + (10^60)^1 + (10^60)^2 + .... + (10^60)^(3만-1))
= A X B ( B = ( 1 + (10^60)^1 + (10^60)^2 + .... + (10^60)^(3만-1)) )

결국 A가 어떤 수의 배 수인지 판별하는 문제가 됩니다.

배수 판정법에서 유명한 것은 3과 9의 배수 판정법이죠. 자리수를 합해서 3또는 9의 배수면
본래수도 3또는 9의 배수가 됩니다.
아래에 배수 판정법을 정리해 봤습니다.
일단 3의 배수가 되는지 각 수를 더해보면 280.
3의 배수가 아니므로 A는 3의 배수가 아닙니다.
끝자리 2개가 10이므로 4의 배수도 아닙니다.
3의 배수가 아니므로 6이 배수도 아닙니다.
각 세자리씩 더하고 빼고하면 7의 배수 A는 7의 배수습니다.

그럼 답은 7일까요?
아닙니다. 숫자 B도 어떤 수의 배수가 될 수 있기 때문입니다.
이번에는 B를 판정해 봅니다.

각 자리를 다 더하면 30000 . 3의 배수 이므로 B는 3의 배수입니다.
그러므로 AXB는 3배수 이자 7의 배수 입니다.

답은 3 입니다.


=== 배수 판정법

2의 배수 : 짝수
3의 배수 : abcdefghi 같은 수가 있을 때 a+b+c+d+e+f+g+h+i 가 3의 배수면 abcdefghi도 3의 배수
4의 배수 : 끝에서 2자리의 수가 4의 배수 , adcdefg 에서 fg가 4의 배수면 adcdefg는 4의 배수
5의 배수 : 끝자리가 0 또는 5
6의 배수 : 2의 배수이며 3의 배수
7의 배수 : abcefghig가 있을 때 abc-efg+hig 가 7의 배수이면 abcefghig는 7의 배수
8의 배수 : 끝 세자리가 8의 배수이면 전체수도 8의 배수
9의 배수 : abcdefghi 같은 수가 있을 때 a+b+c+d+e+f+g+h+i 가 3의 배수면 abcdefghi도 3의 배수
10의 배수 : 끝자리 0이면 10의 배수
11의 배수 : abcdefg 같은 수가 있을 때 a-b+c-d+e-f+g 가 11의 배수면 abcdefghi도 11의 배수
abcefghig가 있을 때 abc-efg+hig 가 11의 배수이면 abcefghig는 11의 배수
12의 배수 : 4의 배수이며 3의 배수
13의 배수 : abcefghig가 있을 때 abc-efg+hig 가 13의 배수이면 abcefghig는 13의 배수
14의 배수 : 7의 배수이며 2의 배수
15의 배수 : 5의 배수이며 3의 배수
16의 배수 : 끝 네자리가 8의 배수이면 전체수도 8의 배수
17의 배수 : abcdef 가 있을때 abcde - 5f 가 17의 배수이면 abcdef도 17의 배수
18의 배수 : 9의 배수이며 2의 배수
19의 배수 : abcdef 가 있을때 abcde + 2f 가 19의 배수이면 abcdef도 19의 배수
등등등
합성서는 거듭제곱꼴로 나타나는 것만 주의 하면 인수분해 된 수들의 공배수가 되는지를
생각해 보면 판별 가능 하고
2의 거듭 제곱 꼴은 2^n의 배수 판정은 끝에서 n자리 숫자까지가 2^n의 배수 인지 판단
3^3 이상의 거듭 제곱 꼴은 판정법을 잘 모르겠습니다.