тайм-аут для большого ввода в 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, а его выходное значение должно быть «ДА». поскольку (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");
}
}