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.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");
}
}

Answer 3

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");
        }
    }
}