java - "Equations"hackerrank 挑战

Question

我在 hackerrank.com 上的“方程”挑战赛的一些测试用例上遇到了问题。这是问题所在:https://www.hackerrank.com/challenges/equations .
我很确定我理解了逻辑，但是我的程序中仍然存在错误(或者我的逻辑中存在缺陷)。

public class Solution
{
    public static void mark(boolean[] a, int i, int n) //sieve util
    {
        int num = i*2;
        while(num <= n)        
        {
            a[num] = true;
            num += i;
        }
    }
    public static long legendre(int n, int p) //get prime power   
    {
        long ans = 0;
        int k = p;
        while(n/k != 0)        
        {
            ans += (long)n/k;
            k *= p;
        }
        return ans;
    }
    public static void main(String[] args)
    {
       long mod = 1000007; 
       int n;
       Scanner input = new Scanner(System.in);
       n = input.nextInt();
       boolean[] a = new boolean[n+1];
       for(int i = 2; i <= n; ++i) //sieve
       {
           if(a[i] == false)
           {
               mark(a,i,n);
           }
       }      
       boolean isEven = true;
       long ans = 1, power = 1;
       for(int i = 2; i <= n; ++i)
       {
           if(a[i] == false)
           {
               power = legendre(n,i);
               if(power%2 == 1)
               {
                   isEven = false;
               }
               ans *= (2*power+1);
               ans %= mod;
           }
       }
       if(isEven == true) //symmetric solution
            ans -= 1;
       if(n == 1) //special case
            System.out.println(1);
       else
            System.out.println(ans);                  
    }
}

我尝试做的事情:创建一个素值表，然后获取 n! 的每个素因子的幂。我使用了这个公式:http://www.cut-the-knot.org/blue/LegendresTheorem.shtml 。我的程序为 n = 105387 生成了正确的输出(即 629416)，但对于 n = 131399，我的输出为 598995(应该是856428)。

这个问题之前也被问过:Sample testcase for Interviewstreet: Equations有人问“N=131399 的输出是什么，我得到 598995，但它给出了错误。 – peeyush 2012 年 5 月 26 日 20:33”显然我的特殊错误并不是独一无二的。

Answer 1

调用legendre(131399,46349)时，变量k溢出。

将此变量的类型从 int 更改为 long。

<小时/>

顺便说一句，您可以通过在循环内添加断言来轻松跟踪它:

if (k < 0)
    System.out.println(k);