Иногда, когда я лениво пытаюсь учесть, какое число появляется передо мной, через некоторое время я понимаю, что это проще, чем я думал. Возьмем, 2156к примеру: мне в конечном итоге пришло в голову, что и то, 21и другое 56является кратным 7, и поэтому, безусловно 2156 = 21 x 100 + 56, также является кратным 7.

Ваша задача - написать некоторый код, который идентифицирует числа, которые легче вычислить из-за совпадения такого рода.

Точнее:

Напишите программу или функцию, которая принимает положительное целое число в nкачестве входных данных и возвращает истинное значение, если существует такой делитель d(больше чем 1), который nможно разделить на два, чтобы получить два положительных целых числа, каждое из которых кратно d; вернуть ложное значение, если нет.

• «Нарезанный пополам» означает то, что вы думаете: обычное представление base-10, nразделенное в некоторой точке на переднюю половину и заднюю половину, чтобы получить два других целых числа base-10. Это нормально, если второе целое имеет начальный ноль (но учтите, что оно должно быть положительным целым числом, поэтому разбиение 1230на 123и 0недопустимо).
• Истинные и ложные значения могут зависеть от ввода. Например, если любое ненулевое целое число является правдивым на выбранном вами языке, вы можете вернуть делитель dили одну из «частей» n(или nсебя в этом отношении).
• Например, любое четное число, содержащее не менее двух цифр в наборе {2, 4, 6, 8}, даст истинное значение: просто разделите его после первой четной цифры. Также, например, любое простое число nбудет давать ложное значение, как и любое однозначное число.
• Обратите внимание, что достаточно рассмотреть простые делители d.
• Вы можете предположить, что ввод действителен (то есть, положительное целое число).

Это код-гольф , поэтому выигрывает самый короткий код в байтах. Но решения на всех языках приветствуются, поэтому мы можем стремиться к созданию самого короткого кода на каждом языке, а не только самого короткого кода в целом.

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

(Вам нужно только вывести истинное или ложное значение; приведенные ниже аннотации приведены только для пояснения.) Некоторые входные данные, которые дают истинные значения:

39  (3 divides both 3 and 9)
64  (2 divides both 6 and 4)
497  (7 divides both 49 and 7)
990  (splitting into 99 and 0 is invalid; but 9 divides both 9 and 90)
2233  (11 divides both 22 and 33)
9156  (3 divides both 9 and 156; or, 7 divides both 91 and 56)
11791  (13 divides both 117 and 91)
91015  (5 divides both 910 and 15)
1912496621  (23 divides both 1912496 and 621; some splittings are multiples of 7 as well)
9372679892  (2473 divides both 937267 and 9892; some splittings are multiples of 2 as well)

Некоторые входные данные, которые дают ложные значения:

52
61
130  (note that 13 and 0 is not a valid splitting)
691
899
2397
9029
26315
77300  (neither 7730 and 0 nor 773 and 00 are valid splittings)
2242593803

¹ да, я действительно делаю это

Сетчатка , 31 29 байт

,$';$`
\d+
$*
;(11+)\1*,\1+;

Попробуйте онлайн!

Выводит положительное целое число для допустимых входных данных и ноль для недействительных.

Я не рекомендовал бы ждать больших тестовых случаев ...

объяснение

,$';$`

В каждой позиции ввода вставьте запятую, затем все до этой позиции, затем точку с запятой, затем все после этой позиции. Что это делает? Это дает нам все возможные разбиения числа (разделить ,, разделить на ;), а затем ввод снова в конце. Таким образом, вход 123становится

,123;1,23;12,3;123,;123
     ^     ^     ^

где я пометил исходные символы ввода (то, что не помечено, это то, что мы вставили). Обратите внимание, что это создает недопустимые расщепления, которые не являются фактическими расщеплениями, и также не имеет значения, является ли конечный компонент всеми нулями, но мы избежим их принятия позже. Преимущество создания недопустимых разделений состоит в том, что мы знаем, что каждое допустимое разделение имеет ;перед и после него, поэтому мы можем сохранить два байта на границах слов.

\d+
$*

Перевести все числа в одинарные.

;(11+)\1*,\1+;

Сопоставьте разбиение, сопоставив обе половинки как кратные некоторого числа, которое по крайней мере 2.

Брахилог (2), 8 байт

~c₂ḋᵐ∋ᵐ=

Попробуйте онлайн!

объяснение

~c₂ḋᵐ∋ᵐ=
~c₂       Split the input into two pieces
    ᵐ ᵐ   On each of those pieces:
   ḋ ∋      Choose a prime factor
       =  such that both the chosen factors are equal

Ясно, что если одно и то же число (больше 1) делит обе части, одно и то же простое число будет делить обе части. Требование, чтобы фактор был простым, аккуратно запрещает 1 как фактор. Это также предотвращает 0выбор литерала как сегмента числа (потому что 0он не имеет простой факторизации и приведет ḋк сбою).

Нет необходимости проверять соответствие внутренних нулей; если раскол xи 0yдействует, x0и yбудет работать так же хорошо (и в другую сторону, если x0и yработает, то есть работающее решение , независимо от того , xи 0yбудет работать или нет).

Полная программа на брахилоге, как эта, возвращает логическое значение; true.если есть какой-то способ запустить его без сбоев (т.е. сделать выбор таким, чтобы не возникало ошибок), false.если все пути ведут к сбою. Это именно то, что мы хотим здесь.

Желе , 14 12 11 10 байт

ŒṖḌo1g/€P>

Спасибо @JonathanAllan за отыгрывание 1 байта!

Попробуйте онлайн!

Как это работает

ŒṖḌo1g/€P>  Main link. Argument: n

ŒṖ          Compute all partitions of n's decimal digits.
  Ḍ         Undecimal; convert each array in each partition back to integer.
   o1       OR 1; replace disallowed zeroes with ones.
     g/€    Reduce (/) each (€) partition by GCD (g).
            The last GCD corresponds to the singleton partition and will always be
            equal to n. For a falsy input, all other GCDs will be 1.
        P   Take the product of all GCDs.
         >  Compare the product with n.

Mathematica, 63 62 байта

(1 байт благодаря Грегу Мартину)

1<Max@@GCD@@@Table[1~Max~#&/@Floor@{Mod[#,t=10^n],#/t},{n,#}]&

Это функция, которая принимает целое число в качестве входных данных и возвращает Trueили False. Если вы проверите это на большом количестве, принесите книгу, чтобы прочитать, пока вы ждете.

Объяснение:

• Floor@{Mod[#,t=10^n],#/t}арифметически разбивает входные данные на последние nцифры и оставшиеся m-nцифры (где mобщее количество цифр).
• Table[1~Max~#&/@...,{n,#}] делает это для каждого n до входного номера. (Это слишком много. Нам нужно сделать это только до количества цифр на входе, но этот способ сохраняет байты и все равно дает правильный результат.) 1~Max~#&/@Бит избавляется от нулей, поэтому такие числа, как 130 -> {13,0}не считать как True.
• 1<Max@@GCD@@@... находит наибольший общий делитель каждой из этих пар и проверяет, являются ли какие-либо из этих делителей больше 1. Если они есть, мы нашли способ разделить число на множители.

Haskell , 57 байт

x#n|b<-mod x n=x>n&&(b>0&&gcd(div x n)b>1||x#(10*n))
(#1)

Попробуйте онлайн! Использование:, (#1) 2156возвращает TrueилиFalse

C 145 142 139 138 135 байтов

i,a,b;f(){char s[99];scanf("%s",s);for(char*p=s;*p++;)for(b=atoi(p),i=*p,*p=0,a=atoi(s),*p=i,i=1;i++<b;)*s=a%i-b%i|b%i?*s:0;return!*s;}

JavaScript (ES6), 74 71 70 байт

f=(s,t='',u)=>u?s%t?f(t,s%t,1):t:s&&f(t+=s[0],s=s.slice(1),1)>1|f(s,t)

<input oninput=o.textContent=f(this.value)><span id=o>

Принимает ввод в виде строки, что удобно для фрагмента. Редактировать: 3 байта сохранены благодаря @ user81655.

Python 3 133 118 117 байт

i,j=int,input()
from fractions import*
print(any(i(j[k:])*i(j[:k])*~-gcd(i(j[k:]),i(j[:k]))for k in range(1,len(j))))

Конечно, не самый короткий, возможно, может быть немного сокращен. Работает O(n)вовремя. Входные данные принимаются в формате, \d+а выходные данные - в формате (True|False)согласно булевому значению Python по умолчанию
-3 байта благодаря Dead Possum
-15 байтов благодаря ovs
-1 байт благодаря этому парню

QBIC , 91 90 байт

;_LA|[a-1|B=left$(A,b)┘C=right$(A,a-b)┘x=!B!┘y=!C![2,x|~(x>1)*(y>1)*(x%c=0)*(y%c=0)|_Xq}?0

Объяснение:

;               Get A$ from the command prompt
_LA|            Get the length of A$ and place it in a% (num var)
[a-1|           for b%=1; b% <= a%-1; b%++
B=left$(A,b)    break A$ in two components on index b%
C=right$(A,a-b)
x=!B!┘y=!C!     Convert both parts from string to num, assign to x% and y%
[2,x|           FOR c% = 2; c% <= x%; c%++

This next IF (~ in QBIC) is a bit ... iffy. It consists of a set of comparators.
Each comparator yields a -1 or a 0. We take the product of these. At any failed
comparison this will yield 0. When successful, it yields 1, which is seen as true by QBasic.

~(x>1)*(y>1)        IF X>1 and Y>1 --> this stops '00' and '1' splits.
*(x%c=0)*(y%c=0)    Trial divide the splits on loop counter c%.

|_Xq            Success? THEN END, and PRINT q (which is set to 1 in QBIC)
}               Close all language constructs (2 FOR loops and an IF)
?0              We didn't quit on match, so print 0

Python 3 , 70 69 байт

import math
f=lambda n,d=1:n>d and n%d*~-math.gcd(n//d,n%d)+f(n,10*d)

Попробуйте онлайн!

Perl 5 , 46 байт

43 байта кода + 3 байта для -pфлага.

s~~$\|=grep!($`%$_|$'%$_),2..$`if$`*$'~ge}{

Попробуйте онлайн! или попробуйте эту модифицированную версию, допускающую несколько входов.
Вы, вероятно, не хотите пробовать это на самом большом входе, так как это может занять (очень много) некоторое время.

Пояснения:
мы перебираем каждую позицию в слове с s~~~g, $`содержащим числа до и $'числа после. Если $`*$'это правда (это означает, что ни один не является пустым, и ни один не является 0), то мы проверяем, если число между 2 и $`делит их обоих (с grep!(...),2..$`). Если это так, $\|=..будет установлено $\ненулевое значение, которое неявно печатается в конце благодаря -pфлажку.

Python 2 , 69 байт

f=lambda n,d=10,k=2:k<d<n and(n/d%k+n%d%k<1<n%d)|f(n,d,k+1)|f(n,10*d)

Использует рекурсию вместо встроенных в GCD.

Попробуйте онлайн!

Как это работает

Когда f вызывается с одним-тремя аргументами (по умолчанию d равно 10 , k - 2 ), сначала проверяется значение выражения k<d<n. Если выполняются неравенства k <d и d <n , выполняется следующее выражение и andвозвращается его значение; в противном случае, f просто вернет False .

В первом случае мы начнем с оценки выражения n/d%k+n%d%k<1<n%d.

d всегда будет степенью десяти, поэтому n/dи n%dэффективно разделим десятичные цифры на n на две части. Эти срезы делятся на k в том и только в том случае, если n/d%k+n%d%kзначение равно 0 , что проверяется путем сравнения результата с 1 .

Поскольку часть требований состоит в том, что оба среза должны представлять положительные целые числа, значение n%dтакже сравнивается с 1 . Обратите внимание, что 1 не имеет простых делителей, поэтому более дорогое сравнение с 0 не требуется. Также обратите внимание, что d <n уже гарантирует, что n/dбудет иметь положительное целое число.

Наконец, он рекурсивно все f(n,d,k+1)(пробует следующий потенциальный общий делитель) и f(n,10*d)(пробует расщепление) и возвращает логическое ИЛИ всех трех результатов. Это означает, что f вернет True, если (и только если) k является общим делителем n / d и n% d или то же самое верно для большего значения k и / или большей степени, равной десяти d .