일단 F(x) = 1이 되는 모든 수를 구하면 됨.

이 수들은 생각보다 적다는 사실을 알 수 있는데,

주어진 문제의 해는 x^2 = x (mod 10^k)에서 k = 1...10 일 때 가능한 x들의 부분집합임을 알 수 있음.


이 때 x(x-1) = 0 (mod 2^k) 이면서 (mod 5^k) 이어야 하므로, 하나의 k에 대해서 해는 4개라는 사실을 알 수 있음.
따라서 F(x) = 1의 해는 100억 미만의 범위에서 많아야 40개임.


그러면 그 해를 어떻게 구하는가? 그냥 전수조사 해도 되지만 F(x) = 1의 해는 특징이 있음
625를 생각해보면 F(625) = 1 이려면 F(25) = 1 이어야 함


따라서 마지막 자리부터 시작해서 해가 되는 얘들 앞에만 0~9를 붙여주는 방식으로 탐색을 할 수 있음


viewimage.php?id=3dae&no=24b0d769e1d32ca73cee84fa11d02831cd949b6924735c7cb75a680f5c9a0fd5d7a4d228dc2d83ef75ce9f3831db12b8174dd0fd89d495a6ef

따라서 100억 이하의 해는


1
5
6
25
76
625
376
9376
90625
890625
109376
2890625
7109376
12890625
87109376
212890625
787109376
1787109376


이것만 있음을 알 수 있음