Вычислить p-адическую норму рационального числа

Напишите функцию или программу, которая принимает 3 целых числа m,n,p(где pположительное простое число) в качестве входных данных и выводит p-адическую норму (обозначаемую |m/n|_p) как (полностью уменьшенную) дробь. У Ферма, как известно, только очень маленькие поля, но неизвестно, что у него был очень маленький экран компьютера. Поэтому постарайтесь сделать код максимально коротким, чтобы он помещался на экране Ферма!

Определение

При условии простого числа pкаждая дробь m/nможет быть однозначно записана (игнорируя знаки) как (a/b)* p^eтаковая, которая eявляется целым числом и не pделит ни, aни b. Р-адической нормой в m/nэто p^-e. Существует особый случай, если дробь 0: |0|_p = 0.

Выходной формат должен быть x/y(например 1/3, для целых чисел разрешены оба 10или эквивалентно 10/1, для отрицательных чисел должен быть начальный минус, например -1/3)

подробности

Программа должна использовать stdin / stdout или просто состоять из функции, которая возвращает рациональное число или строку. Вы должны предположить, что ввод m/nне полностью уменьшен. Вы можете предположить, что pэто простое число. Программа должна иметь возможность обрабатывать целые числа от -2^28до 2^28и не должна занимать более 10 секунд.

Не допускаются встроенные функции факторизации и первичной проверки, а также встроенная базовая диалоговая система и встроенная функция, которая вычисляет p-adic оценку или норму.

Примеры (украдено из википедии ):

x = m/n = 63/550 = 2^-1 * 3^2 * 5^-2 * 7 * 11^-1
|x|_2 = 2
|x|_3 = 1/9
|x|_5 = 25
|x|_7 = 1/7
|x|_11 = 11
|x|_13 = 1

Интересные мелочи

(Не обязательно знать / читать для этой задачи, но, возможно, приятно читать в качестве мотивации.)

(Пожалуйста, поправьте меня, если я использую неправильные слова или что-то не так, я не привык говорить об этом на английском языке.)

Если вы рассматриваете рациональные числа как поле, то p-адическая норма индуцирует p-адическую метрику d_p(a,b) = |a-b|_p. Затем вы можете заполнить это поле в отношении этой метрики, это означает, что вы можете создать новое поле, где все последовательности Коши сходятся, что является хорошим топологическим свойством. (Что, например, рациональные числа не имеют, но действительные имеют.) Эти p-адические числа , как вы могли догадаться, часто используются в теории чисел.

Другим интересным результатом является теорема Островского, которая в основном гласит, что любое абсолютное значение (как определено ниже) для рациональных чисел является одним из следующих трех:

• Тривиальное: |x|=0 iff x=0, |x|=1 otherwise
• Стандарт (реальный): |x| = x if x>=0, |x| = -x if x<0
• П-адик (как мы его определили).

Абсолютное значение / метрика - это просто обобщение того, что мы считаем расстоянием . Абсолютное значение |.|удовлетворяет следующим условиям:

• |x| >= 0 and |x|=0 if x=0
• |xy| = |x| |y|
• |x+y| <= |x|+|y|

Обратите внимание, что вы можете легко построить метрики из абсолютных значений и наоборот: |x| := d(0,x)или d(x,y) := |x-y|, так что они почти одинаковы, если вы можете добавить / substract / multiply (то есть в интегральных областях). Конечно, вы можете определить метрику на более общих наборах без этой структуры.

Юлия, 94 80 75 байт

f(m,n,p)=(k=gcd(m,n)
g(m)=m%p>0?g(m÷p)p:1
m!=0?print(g(n÷k),/,g(m÷k)):0)

Примечание: использование перевода строки вместо точек с запятой для удобства чтения - будет работать одинаково в любом случае.

Это довольно просто - g(m,n)функция использует recursion и remainder ( %) для извлечения p^nкоэффициента из входных данных m, n=1по умолчанию, а затем умножается на pна каждом шаге рекурсии, так что результат будет p^n. Код применяет это к n/gcd(m,n), а затем к, m/gcd(m,n)чтобы получить соответствующее выражение. k=gcd(m,n)используется, чтобы избежать вычисления gcd(m,n)дважды, чтобы сохранить символы. m!=0это тест для обработки случая, когда x=0.

Вывод имеет форму N/1или, 1/Nв зависимости от случая, где Nесть p^e.

J, 35 34 байта

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:

Это двоичный глагол, который принимает простое число в pкачестве левого аргумента, а массив - в m nкачестве правого аргумента. Он всегда печатает косую черту /и возвращает 0/1if m = 0. Используйте это так:

  f =: (,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:
  5 f 63 550
25/1

объяснение

В x:повороты на повышенной точности, так как мы обработки очень больших чисел. Остальная часть кода работает следующим образом:

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         Power: this gives the array p^n p^m
                         +.       Take element-wise GCD with
                           |.@]   the rotated array n m; this gives
                                  the largest powers of p that divide n and m
                      <.          Take element-wise minimum with
                     [            The array m n to handle the m=0 case correctly
              %+./                Divide this array by its GCD to get it to lowest terms
        &":/                      Convert both elements to strings
 ,'/'&,                           Insert the slash '/' between them

CJam, 42 байта

q~)\_:*g_sW<o@*28#f{{{_@\%}h;}:G~}_~Gf/'/*

Это завершается с ошибкой (после печати 0) для ввода 0. Попробуйте онлайн в интерпретаторе CJam .

Stax , 32 байта

éE▌ΦΔΘao£╙)ΩuÅI~AAε3∞xC█&½╤%╩▌ïö

Запустите и отладьте его

Должен быть в состоянии сделать его короче. Нативная поддержка фракции Stax довольно аккуратна.

ASCII эквивалент:

hY{y:+y|aEGsG-ys|**}0?}0{^scxHY%Cy/sWd