求有理数的p-adic范数

Question

计算有理数

的p进模

编写一个函数或程序，它以3个整数m,n,p (其中p是一个正素数)作为输入，并以一个(完全约简的)分数输出p进位范数(由|m/n|_p表示)。众所周知，费马的利润率很小，但不为人所知的是他只有一个非常小的电脑屏幕。因此，尽量使代码尽可能短，以适应费尔马的屏幕！

定义

给定素数p，可以将每个分数m/n唯一地写入(忽略符号)为(a/b)* p^e，这样e是整数，p既不对a也不对b进行除法。m/n的p进位范数是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-adic范数就会导出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
• P-进(按我们的定义)。

绝对值 / 公制只是我们所认为的距离的推广。绝对值|.|满足以下条件：

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

请注意，您可以很容易地从绝对值构造度量，反之亦然：|x| := d(0,x)或d(x,y) := |x-y|，因此如果您可以添加/减/乘(即积分域)，它们几乎是相同的。当然，您可以在更一般的集合上定义一个度量，而不需要这种结构。

Answer 1

CJam，42字节

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

THis完成输入0的错误(在打印0之后)。在CJam解释器网上试一试。

Answer 2

斯塔克斯，32 字节数

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

运行并调试它

应该能缩短时间。Stax对分数的原生支持是相当干净的。

ASCII相当于：

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