1

我正在尝试找到解决方案的数量

       x^a (mod b) =c with 0<=x<=u

其中 b<=50 但 a 和 u 可以很大。我的方法是从 0 到 min(b,u) 遍历 x 的每个值，如果它满足等式添加 ceil((ux)/b) （以说明 x 的值的数量大于 b但在 b) 的乘法域中等价于解的数量。我不确定我的算法的正确性。我可以将我的方法扩展到多个变量，例如是否存在

    (x^a + y^a) (mod b)=c

我可以生成所有无序的 x 和 y 对，使得 x<=y 直到 (x,y)<=min(b,u) 并再次计算 i=ceil((ux)/b) 和 j=ceil((uy )/b) 并将总和相乘为：

            t={i+i*(i-1)*2 if x=y , i*j*2 if x!=y }

并对 t 求和。我想知道我的算法是否正确以及是否有其他更有效的算法。

4

1 回答 1

0

是的，如果 x^a mod b = c 则 (x+b)^a mod b = c。所以到目前为止总共会有 1 + floor((ux)/b) 的解决方案。您只需要记住在搜索从 (x+1) 到 min(u,b) 的其他解决方案时跳过这些数字。

该概念适用于 2 个变量，但计算量更大。您求解 x^a mod b = d 并将计数保存为 T[d]，其中 0 ≤ d < b。你可能会问为什么 0 ≤ d < b 而不是 0 ≤ d ≤ c。这个例子就是为什么：如果 c=7 和 b=35 那么 (x,y) 这样 x^a mod 35 = 8 和 y^a mod 35 = -1 ≡ 34 也是一个解决方案。

然后解决方案的总数与您建议的类似，但我不打扰单独处理 x=y 和 x≠y：

for (i=0 ; i < b ; i++)
   count += T[i]*T[(b +c -i)%b];
于 2013-08-04T19:57:36.117 回答