자릿수 조합 방법은 무엇입니까?

Question

주어진 숫자가 N (일반 숫자) 인 경우 N-digit 숫자를 출력해야합니다 (예 : 사각형의 마지막 숫자가 987654321과 같음).

1<=N<=10^6

가 간단 조합론 문제가 될 수

. 나는 잘 모르겠다. 이 문제에 대한 알고리즘을 찾으려고합니다. 이 문제를 해결하는 가장 좋은 알고리즘은 무엇입니까?

Answer 1

질문 :

이 x^2 mod 1000000000 = 987654321을 만족하는 n 개의 자리 숫자 x의 수를 찾습니다. < N = 9

대한 우선

1. 용액 (X)를 만족 x^2 = 987654321, 0 <= x < 1000000000의 값을 계산한다.
10^9 개의 정수만 확인하면되므로 PC에서 미리 계산할 수 있습니다.

I의 값을 계산하고, 결과는 다음 하였다
Result: 111111111,119357639,380642361,388888889,611111111,619357639,880642361,888888889

따라서 n <= 8 경우 응답이 제로이고, n = 9 경우 응답은 제

2이다. n> = 10에 대한 해답
x^2 mod 1000000000은주기가 있기 때문에이 사실을 증명할 수 있습니다 길이 10^9.

• 는 0 <= x < 10^9 8 개 솔루션이 있습니다.
• 10^9 <= x < 2*10^9에는 8 가지 해결책이 있습니다.
• 2*10^9 <= x < 3*10^9에는 8 개의 솔루션이 있습니다.
• k*10^9 <= x < (k+1)*10^9 (k is an integer)에는 8 개의 솔루션이 있습니다.

그래서 이러한 것을 말할 수 있습니다.

• 0 <= x < 10^9에는 8 가지 해결책이 있습니다.
• 0 <= x < 10^10에는 80 개의 솔루션이 있습니다.
• 0 <= x < 10^11에는 800 개의 솔루션이 있습니다.

따라서,

• 모두 10 자리 숫자 72 개의 솔루션이있다.
• 모든 11 자리 숫자에 720 개의 솔루션이 있습니다.
• 모든 12 자리 숫자에 7200 개의 솔루션이 있습니다.

그래서, 당신은 출력이 "72"+ (N-10 0의) 경우 N> 9.

3. 결론

• 만약 N < = 8 대답은 0입니다.
• n = 9 인 경우 대답은 8입니다.
• n> = 10 인 경우 대답은 72 * 10^(n-10)입니다.