Задача

Дайте ввод rи nнайдите первые nнатуральные числа, xтакие, что если мы повернем первую цифру в последнее место, мы получим x/r.

Вы можете предположить, что 2 <= r <= 9и 1 <= n <= 65535.

Вы можете написать программу, которая принимает входные данные из аргументов stdin или командной строки; или вы можете написать функцию, которая принимает rи в nкачестве параметров. Вывод, однако, должен быть в стандартный вывод. Выходные данные должны быть по одной строке на значение x, отформатированные x/r=yв порядке возрастания x.

Ваше решение должно быть в состоянии обработать все действительные случаи в течение одной минуты на приемлемом настольном компьютере.

Контрольные примеры

Вход: 4 5
Выход:

102564/4=25641  
205128/4=51282  
307692/4=76923  
410256/4=102564  
512820/4=128205

Вход: 5 1
Выход:714285/5=142857

Это код-гольф, поэтому выигрывает минимум байтов. Победивший ответ будет принят через 4 недели (2014-09-19).

Кредиты по этому вопросу идут моему коллеге, который позволил мне разместить этот вопрос здесь :)

Хаскелл, 182 179

Вторая версия, возможно, в дальнейшем пригодна для игры в гольф, но на этот раз с «правильным» алгоритмом. В частности, он завершается в течение нескольких минут с помощью r=4и n=65535, но опять же мой компьютер не является ни разумным, ни настольным компьютером, так что есть вероятность, что это останется в течение минуты на других машинах.

n#r=take n$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words

Он основан на идее x=10^k*a + m, где его первая цифра 0≤a≤9перемещается в конец для получения y=10*m+a. Немного математики показывает , что mможет быть получено как a*(10^k-r)/(10*r-1), поэтому мы просто сканировать aболее [1..9]для каждого kот 0 до бесконечности, и сохранить и напечатать первые nрезультаты , для которых приведенное выше выражение для mявляется интегралом.

fromIntegralТребуется потому , что readИНГ список с nодним из своих элементов main, в сочетании с использованием nв take, вынудит rна Intвсем, что приводит к неприятным переткам с большими числами в вопросе. Я мог бы использовать genericTake, но это требует import.

Этот код также имеет преимущество, заключающееся в том, что он почти тривиален для расширения на базы, отличные от 10.

Входные данные считываются stdin, два значения могут быть разделены любым пробелом.

Pure Bash (без внешних утилит), 80 байт

for((;++x,c<$2;));{
y=$[10#${x:1}${x:0:1}]
((y*$1==x))&&echo $x/$1=$y&&((c++))
}

Обратите внимание, что bash выполняет только целочисленную арифметику, а не с плавающей запятой, поэтому мы проверяем, если x == y * rвместо x / r == y. Также умножение должно быть быстрее. Тем не менее, это далеко не соответствует требованиям производительности.

Выход:

$ ./rotdiv.sh 4 5
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
$ ./rotdiv.sh 5 1
714285/5=142857
$ 

С 468

#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}

(Некоторые символы новой строки, не учитываемые в счетчике байтов, были добавлены выше для устранения полос прокрутки. Да, последний символ новой строки считается.)

Ожидает аргументы в командной строке и предполагает, что стандартный вывод принимает ASCII. Время выполнения - O (количество выводимых байтов) = O (n * n).

Нет, я не могу использовать printf. Это занимает слишком много времени и заставляет программу превышать минуты на моем рабочем столе. На самом деле, некоторые тестовые случаи занимают около 30 секунд.

Алгоритм обрабатывает выходные данные как строки, а не числа, так как они быстро становятся огромными, и в выходных данных есть сильные шаблоны.

Немного не одураченный

#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
    for (int i=0; i <= repeats; ++i)
        fputs(num, stdout);
    printf("/%c=", '0'+r);

    /* Assume the repeated num is a solution. Just move the first
       digit and skip any resulting leading zeros. */
    const char* num_tail = num;
    ++num_tail;
    while (*num_tail=='0')
        ++num_tail;
    fputs(num_tail, stdout);
    while (repeats--)
        fputs(num, stdout);
    printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
   decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
    r = atoi(argv[1]);
    int n = atoi(argv[2]);
    int q = 10*r-1;
    int d = 0;

    /* Populate the strings in sol[]. */
    while (d++<9) {
        int p = r*d;
        char* sol_str = sol[d];

        /* Do the long division p/q in decimal, stopping when the remainder
           is the original dividend. The integer part is always zero. */
        do {
            p *= 10;
            *sol_str++ = p/q + '0';
            p %= q;
        } while (p != r*d);
    }

    /* Output the answers. */
    d = 1;
    int repeats = 0;
    int r5x7_repeats = 0;
    while (n--) {
        if (r==5 && r5x7_repeats<6) {
            show_line(x[7], 7*repeats + r5x7_repeats);
        } else {
            if (r==5 && d==7)
                show_line(x[d], 7*repeats + 6);
            else
                show_line(x[d], repeats);
            if (++d > 9) {
                d = 1;
                ++repeats;
                r5x7_repeats = 0;
            }
        }
    }
}

доказательство

что программа решает проблему:

(В доказательстве принимайте все операторы и функции за реальные математические функции, а не за компьютерные операции, которые их аппроксимируют. ^Обозначает возведение в степень, а не побитовый xor.)

Для ясности я буду использовать функцию ToDecдля описания обычного процесса записи числа в виде последовательности десятичных цифр. Его диапазон - это набор упорядоченных кортежей {0...9}. Например,

ToDec(2014) = (2, 0, 1, 4).

Для положительного целого числа nопределите L(n)количество цифр в десятичном представлении n; или же,

L(n) = 1+floor(log10(n)).

Для положительного целого kи неотрицательного целого числа nс L(n)<k, определите, Rep_k(n)чтобы быть действительным числом, полученным путем добавления нулей перед десятичными цифрами n, если необходимо получить kобщее количество цифр, и затем бесконечно повторяя эти kцифры после десятичной точки. Например

Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...

Умножение Rep_k(n) * 10^kдает цифры nперед десятичной запятой и цифры (дополненные нулями) nбесконечно повторяющиеся после десятичной запятой. Так

Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)

Учитывая положительное целое число r, предположим, что xэто решение проблемы, и

ToDec(x) = ( x_1, x_2, ..., x_k )

где x_1 != 0и k = L(x).

Чтобы быть решением, xэто кратное r, и

ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).

Применение Rep_kфункции дает хорошее уравнение:

10*Rep_k(x) = x_1 + Rep_k(x/r)

Используя его закрытую форму сверху,

10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)

x_1должен быть в наборе {1 ... 9}. rбыло указано, чтобы быть в наборе {2 ... 9}. Теперь единственный вопрос: для каких значений kприведенная выше формула xдает положительное целое число? Мы рассмотрим каждое возможное значение rиндивидуально.

Когда r= 2, 3, 6, 8 или 9, 10r-1это 19, 29, 59, 79 или 89 соответственно. Во всех случаях знаменатель p = 10r-1прост. В числителе, только 10^k-1может быть кратным p, что происходит, когда

10^k = 1 (mod p)

Множество решений замкнуто при сложении и вычитании, что не приводит к отрицательному числу. Таким образом, набор содержит все кратные некоторого общего множителя, который также является наименее положительным решением для k.

Когда r = 4и 10r-1 = 39; или когда r = 7и 10r-1 = 69знаменатель в 3 раза больше другого простого числа p=(10r-1)/3. 10^k-1всегда кратно 3, и опять никакой другой фактор в числителе не может быть кратным p, поэтому снова проблема сводится к

10^k = 1 (mod p)

и снова все решения кратны наименьшему положительному решению для k.

[Не закончено...]

Питон - 91 90

Вот первый выстрел:

r,n=input();i=1
while n:
 if int(`i`[1:]+`i`[0])*r==i:print'%d/%d=%d'%(i,r,i/r);n-=1
 i+=1

Изменить: Хорошо, это, вероятно, способ замедлить, чтобы удовлетворить необходимый 1-минутный лимит времени для номеров 65K.

JavaScript - 145

function f(a,b){for(d=0;d<b;d++)for(i=1;;i++){c=i/a;if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))console.log(i+'/'+a+'='+c)}}

не в гольф

function f(a,b){
    for(d=0;d<b;d++) //loop for the right amount
        for(i=1;;i++){ //iterating loop
            c=i/a; //actual result of the division
            if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))
                console.log(i+'/'+a+'='+c)
        }
}

Python 3 - 223 179 байт

Python-реализация решения TheSpanishInquisition:

r,n=map(int,input().split());k=0
while 1:
 for a in range(1,10):
  D,M=divmod(a*(10**k-r),10*r-1)
  if M==0:
   print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
   if n==0:exit()
 k+=1

Бег:

• python3 <whatever you named it>.py
• Принимает вход на стандартный ввод
• Входное пространство разделено

Выход:

$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128

Результаты:

https://oeis.org/A092697 является первым значением для каждого r.

Кажется, что только определенные значения k дают ответы, и этот интервал является регулярным. Например, для r = 4:

Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]

Интервалы:

• 2 = 18
• 3 = 28
• 4 = 6
• 5 = 6 (5 кажется аномалией, так как для большинства значений r имеются сгустки 9, 5 сгустков 9 и 1 (только с рабочим = 7), см. Ниже)
• 6 = 58
• 7 = 22
• 8 = 13
• 9 = 44

Это формы https://oeis.org/A094224 .

Используя эти значения, можно построить более эффективную версию:

import math

def A094224(n):
    return [18,28,6,6,58,22,13,44][n-2]


r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
    for a in range(1,10):
        D,M=divmod(a*10**k-a*r,10*r-1)
        if M==0:
            print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
            if n==0:exit()
    k+=A094224(r)

Однако я не могу (пока) доказать, что это продолжается математически.

Результаты для r = 5:

0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]