0보다 큰 정수 x에 대해, 함수 F(x) 를 다음과 같이 정의하자:
x가 10진수로 표현했을 때 K자리인 수라면,
F(x) = (x를 제곱해서 10진수로 표현하고 마지막 K자리를 취한 값이 x와 같으면) 1,
(그렇지 않으면) 0
몇 가지 예를 들면
F(1) = 1 이다. (1*1 = 1)
F(2) = 0 이다. (2*2 = 4)
F(3) = 0 이다. (3*3 = 9)
F(10) = 0 이다. (10*10 = 100)
F(625) = 1 이다. (625*625 = 390625)
어떤 주어진 정수 n에 대해, x < n 이면서 F(x) = 1을 만족하는 정수 x들 중 가장 큰 정수를 찾는 프로그램을 작성하라.
n은 0보다 크고 2147483647 보다는 작다.
===========================================================================================================
선형적인 방법말고 간단하게 풀 수 있는 방법이 있을거 같은데 어떻게들 생각해?
x를 제곱해서 10진수로 표현하고 거기서 마지막 k 자리를 취한 값이 x와 같으려면, (x^2 mod 10^k) = x라는 말이네.
그건 나도 알지 너무 오래 걸린다.
최소한의 연산만 통해서 구할수 있는 방법이 분명있을텐데 ... 흠흠
1의 자리만 하면 되잖어
형들 그게 무슨말이야?
마지막 K자리가 아니고 마지막에서 똑같은거 말이냐
"마지막에서 몇 자리" 이렇게 쓰지 참,,
흠흠.. 눈호랑이형은 무슨말인지?
1의 자리 보는 건 나도 생각했는데 그래도 제곱해야 되는 건 변하지 않음.
(10a + b) ^ 2 = 100a + 10ab + b
ㅋㅋㅋㅋㅋㅋ아무도모르는거야?
내가 볼 땐 끝자리가 5인 수만 가능한 듯.
제곱하는데 숫자들이 밀려 올라가야 하니깐 곱하는 과정에서 10이 나와야 한다는 거임.
근데 1, 6은 힘들고, 그나마 가능성이 보이는 건 2와 5인데 2는 안될 듯.
한자리수 제곱해서 마지막 한자리 일치하는 수 1, 5, 6
이거에 이어서 두자리수 제곱해서 마지막 두자리 일치하는 수 찾으면 X1/X5/X6꼴이 나올거고
세자리수도 마찬가지로 하면 답 쉽게 나옴