数字の組み合わせ方法は？

Question

N（通常の番号）の場合は、N-digitの数値を出力する必要があります。つまり、正方形の最後の数字は987654321に等しくなります。それは、単純な組合せ論の問題である可能性があり1<=N<=10^6

。私はわかりません。私はこの問題のアルゴリズムを見つけようとしています。この問題を解決する最良のアルゴリズムは何ですか？

Answer 1

質問です：

がx^2 mod 1000000000 = 987654321を満たすのn桁の番号xの数を検索します。

1 N = 9 <
最初のためのソリューション、x^2 = 987654321, 0 <= x < 1000000000を満足するxの値を計算します。
10^9個の整数をチェックするだけで済むので、PCで事前にカウントすることができます。

Iの値を算出した結果は、次した
Result: 111111111,119357639,380642361,388888889,611111111,619357639,880642361,888888889

したがって、n <= 8場合答えがゼロであり、n = 9場合答えが8

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のソリューションがあります。だから、

n>は9

3.おわり

• N < = 8の場合ならば、あなただけの、出力 "72" +（N-10 0）に持っています答えが0です。
• n = 9の場合、回答は8です。
• n> = 10の場合、回答は72 * 10 ^（n-10）です。