大输入在 biginteger 中的超时

Question

考虑一下写在纸上的数字1到n的排列。让我们将其元素的乘积表示为 p，将其元素的总和表示为 s。给定一个正整数 n，您的任务是确定 p 是否可被 s 整除。我尝试使用bigInteger概念，但在50个测试用例中，有30个成功通过，但其余的都显示超时，这可能是因为递归。import java.util.*;import java.math.BigInteger;public class TestClass {    static BigInteger factorial(int n){        if(n==0||n==1)            return new BigInteger("1");        return BigInteger.valueOf(n).multiply(factorial(n-1));    }    public static void main(String args[] ) throws Exception {        Scanner s=new Scanner(System.in);        int n=s.nextInt();        int nn=n*(n+1)/2;        BigInteger sum=BigInteger.valueOf(nn);        BigInteger p=factorial(n);            if((p.mod(sum)).equals(BigInteger.valueOf(0)))            System.out.println("YES");        else            System.out.println("NO");   }}对于示例测试用例，输入为 3，其输出应为“YES”，因为 （1+2+3） 除以 （1*2*3）。

Answer 1

尝试删除递归并使用 for 循环计算阶乘。

import java.util.*;

import java.math.BigInteger;

public class TestClass {

static void factorial(long n, long nn){

    BigInteger answer=new BigInteger("1");

    BigInteger sum=BigInteger.valueOf(nn);

    int foundMatch =0;

    for(long i=n;i>0;i--){

        answer=answer.multiply(new BigInteger(String.valueOf(i)));

        if((answer.mod(sum)).equals(BigInteger.valueOf(0)))

        {

            System.out.println("YES");

            foundMatch = 1;

            break;

        }

    }

    if(foundMatch!=1)

    System.out.println("NO");

}

public static void main(String args[] ) throws Exception {

    Scanner s=new Scanner(System.in);

    long n=s.nextLong();

    long nn=n*(n+1)/2;

    factorial(n, nn);    

}

}

Answer 2

import java.util.*;

class TestClass {

    public static int prime(int n)

    {

        int count=0,flag=0;

        if(n==1)

        flag=1;

        if(n==2)

        flag=0;

        else {

        for(int i=2;i<=Math.sqrt(n);i++) {

            if(n%i==0)

            {

                flag=1;

                break;

            }

        }}

        if(flag==1)

        return 1;

        return 0;

    }

    public static void main(String args[] ) throws Exception {

        Scanner s=new Scanner(System.in);

        int t=s.nextInt();

        while(t-->0)

        {

            int flag=0;

            int n=s.nextInt();

            if(n%2==0)

            {

             flag=prime(n+1);   

            }

            else

            {

                flag=1;

            }

        if(flag==1)

        System.out.println("YES");

        else

        System.out.println("NO");

        }

    }

}

Answer 3

您可以使用这样的逻辑：如果阶乘的中间乘积可被总和整除，则整个阶乘也可以被和整除。

import java.math.BigInteger;

import java.util.Scanner;

public class TestClass {

static boolean isFactorialDivisible(int n, BigInteger sum) {

    BigInteger p = BigInteger.ONE;

    for (int i = n; i > 0; i--) {

        p = p.multiply(BigInteger.valueOf(n));

        if (p.mod(sum).equals(BigInteger.ZERO)) {

             return true;

        }

        BigInteger gcd = p.gcd(sum);

        if (!gcd.equals(BigInteger.ONE)) {

            p = p.divide(gcd);

            sum = sum.divide(gcd);

        }

    }

    return false;

}

public static void main(String args[]) throws Exception {

    Scanner s = new Scanner(System.in);

    int n = s.nextInt();

    int nn = n * (n + 1) / 2;

    BigInteger sum = BigInteger.valueOf(nn);

    boolean p = isFactorialDivisible(n, sum);

    if (p)

    System.out.println("YES");

    else

    System.out.println("NO");

}

}