大输入在 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 {&nbsp; &nbsp; public static int prime(int n)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int count=0,flag=0;&nbsp; &nbsp; &nbsp; &nbsp; if(n==1)&nbsp; &nbsp; &nbsp; &nbsp; flag=1;&nbsp; &nbsp; &nbsp; &nbsp; if(n==2)&nbsp; &nbsp; &nbsp; &nbsp; flag=0;&nbsp; &nbsp; &nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; for(int i=2;i<=Math.sqrt(n);i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(n%i==0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }}&nbsp; &nbsp; &nbsp; &nbsp; if(flag==1)&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String args[] ) throws Exception {&nbsp; &nbsp; &nbsp; &nbsp; Scanner s=new Scanner(System.in);&nbsp; &nbsp; &nbsp; &nbsp; int t=s.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; while(t-->0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int flag=0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int n=s.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(n%2==0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;flag=prime(n+1);&nbsp; &nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag=1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if(flag==1)&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("YES");&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("NO");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}

Answer 3

您可以使用这样的逻辑：如果阶乘的中间乘积可被总和整除，则整个阶乘也可以被和整除。import java.math.BigInteger;import java.util.Scanner;public class TestClass {static boolean isFactorialDivisible(int n, BigInteger sum) {&nbsp; &nbsp; BigInteger p = BigInteger.ONE;&nbsp; &nbsp; for (int i = n; i > 0; i--) {&nbsp; &nbsp; &nbsp; &nbsp; p = p.multiply(BigInteger.valueOf(n));&nbsp; &nbsp; &nbsp; &nbsp; if (p.mod(sum).equals(BigInteger.ZERO)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; BigInteger gcd = p.gcd(sum);&nbsp; &nbsp; &nbsp; &nbsp; if (!gcd.equals(BigInteger.ONE)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p = p.divide(gcd);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sum = sum.divide(gcd);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return false;}public static void main(String args[]) throws Exception {&nbsp; &nbsp; Scanner s = new Scanner(System.in);&nbsp; &nbsp; int n = s.nextInt();&nbsp; &nbsp; int nn = n * (n + 1) / 2;&nbsp; &nbsp; BigInteger sum = BigInteger.valueOf(nn);&nbsp; &nbsp; boolean p = isFactorialDivisible(n, sum);&nbsp; &nbsp; if (p)&nbsp; &nbsp; System.out.println("YES");&nbsp; &nbsp; else&nbsp; &nbsp; System.out.println("NO");}}