すべての正の整数は、表現 (基数 10) に 0 と 1 のみが含まれる数値を除算します。
次のことを証明できます。
1、11、111、1111 などから 111... 1 までの数字を考えてみましょう。最後の数字は n+1 桁です。これらの数を m 1、m 2、...、m n+1と呼びます。それぞれを n で割ると余りがあり、これらの余りのうち 2 つが同じでなければなりません。それらは n+1 個ありますが、残りが取ることができる値は n 個しかないためです。これは、有名で有用な「ピジョンホールの原理」の応用です。
剰余が同じ 2 つの数値が m iと m j で、i < j であるとします。次に、大きい方から小さい方を引きます。結果の数値 m i −m jは、j - i 個の 1 とそれに続く i 個のゼロで構成され、n の倍数でなければなりません。
しかし、最小の答えを見つけるにはどうすればよいでしょうか。そして効率的に？
この問題は、n の合計 m を得るために 10 i mod n (各 i に対して、最大で 1 回使用できます) を使用することと同じです。ナップザック問題や部分和問題のようなものです。このようにして、動的計画法がタスクを実行します。
動的計画法では、複雑さはO(k*n)です。k は回答の桁数です。n<10 5の場合、このコードは完全に機能します。
コード：
#include <stdio.h>
#define NUM 2000
int main(int argc, char* argv[])
{
signed long pow[NUM],val[NUM],x,num,ten;
int i,j,count;
for(num=2; num<NUM; num++)
{
for(i=0; i<NUM; pow[i++]=0);
count=0;
for(ten=1,x=1; x<NUM; x++)
{
val[x]=ten;
for(j=0; j<NUM; j++)if(pow[j]&&!pow[(j+ten)%num]&&pow[j]!=x)pow[(j+ten)%num]=x;
if(!pow[ten])pow[ten]=x;
ten=(10*ten)%num;
if(pow[0])break;
}
x=num;
printf("%ld\tdivides\t",x=num);
if(pow[0])
{
while(x)
{
while(--count>pow[x%num]-1)printf("0");
count=pow[x%num]-1;
printf("1");
x=(num+x-val[pow[x%num]])%num;
}
while(count-->0)printf("0");
}
printf("\n");
}
}
PS: このシーケンスはOEISにあります。
現在受け入れられている回答よりも効率的な O(n)-time (実際には n を法とする算術演算) ソリューションがあります。アイデアは、頂点 i が (i*10)%n および (i*10+1)%n に接続している頂点 0..n-1 でグラフを作成し、幅優先検索を使用して辞書編集的に最小のものを見つけることです。 1 から 0 へのパス。
def smallest(n):
parents = {}
queue = [(1 % n, 1, None)]
i = 0
while i < len(queue):
residue, digit, parent = queue[i]
i += 1
if residue in parents:
continue
if residue == 0:
answer = []
while True:
answer.append(str(digit))
if parent is None:
answer.reverse()
return ''.join(answer)
digit, parent = parents[parent]
parents[residue] = (digit, parent)
for digit in (0, 1):
queue.append(((residue * 10 + digit) % n, digit, residue))
return None
これは、最初の 792 個の回答をすばやく取得する方法です。最も単純なコードを定義します。
__author__ = 'robert'
from itertools import product
def get_nums(max_length):
assert max_length < 21 #Otherwise there will be over 2 million possibilities
for length in range(1, max_length + 1):
for prod in product("10", repeat=length):
if prod[0] == '1':
yield int("".join(prod))
print list(get_nums(4))
[1, 11, 10, 111, 110, 101, 100, 1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000]
nums = sorted(get_nums(20))
print len(nums)
solution = {}
operations = 0
for factor in range(1, 1000):
for num in nums:
operations += 1
if num % factor == 0:
solution[factor] = num
break
print factor, operations
if factor not in solution:
print "no solution for factor %s" % factor
break
print solution[787]
max_v = max(solution.values())
for factor, val in solution.items():
if val == max_v:
print factor, max_v
[1, 11, 10, 111, 110, 101, 100, 1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000]
1048575
1 1
2 3
3 10
4 14
5 16
6 30
7 39
8 47
9 558
10 560
11 563
12 591
13 600
14 618
15 632
16 648
17 677
18 1699
19 1724
20 1728
..
..
187 319781
188 319857
..
..
791 4899691
792 5948266
no solution for factor 792
10110001111
396 11111111111111111100
これは、リンクされたリストを使用したC＃ソリューションです
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
public static void print(LinkedList<int> lst)
{
foreach(int i in lst)
{
Console.Write(i);
}
}
static void Main(string[] args)
{
int number = Convert.ToInt32(Console.ReadLine());
int product;
LinkedList<int> list = new LinkedList<int>();
bool Istrue = true;
int range = 1;
while (range <= 10) {
Istrue = true;
product = number * range;
while (product > 0)
{
list.AddFirst(product % 10);
product /= 10;
}
foreach (int i in list)
{
if (i > 1) Istrue = false;
}
if (Istrue) { print(list); break; }
else
{
list.Clear();
}
range++;
}
Console.WriteLine("Done");
string s = Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
class Class1
{
public static void Main()
{
List<string> possibleCombination = new List<string>();
for (int i = 2; i < 10000; i++)
{
possibleCombination.Add(Convert.ToString(i, 2));
}
var input = Console.ReadLine();
long output = 0;
foreach (var item in possibleCombination)
{
if (Convert.ToInt64(item) % Convert.ToInt64(i) == 0)
{
output = Convert.ToInt64(item);
break;
}
}
Console.WriteLine(output);
Console.ReadLine();
}
}
}
私のアルゴリズムは次のようになります:-
1) n 個の可能な数 (最初の n は 10 とします) のソートされたツリーを構築します。したがって、この例では、1,10,11,100,101,110,111... が含まれます。
2)次に、リストをループして、各 no x%GivenNo に対して実行します。
3) それ以外の場合は、ステップ 3 を別の 10 個の数字で繰り返します。