如何检查一个非常大的数字是否是 1 的连续和？

Question

我正在尝试解决这个问题：检查数组的元素是否是从1开始的连续和。输入Q（数组的长度，1≤Q≤10^3），然后根据长度输入元素（ 1≤N[i]≤10^18)。示例：6=1+2+3 打印是。 10=1+2+3+4 打印是。 5=2+3 打印 No 因为它不是 1 的连续总和事情是我的代码在一个小数字上工作，例如 6、10、15。但是我还需要根据条件检查更大的数字（比如 234223743）。我怎样才能简化我的代码？我的代码：

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum =0;
        int x=1;
        int Q = scanner.nextInt();
        int []N=new int [Q];
        for (int i = 0 ; i<Q;i++){
            N [i]= scanner.nextInt();
            while (sum <N[i]){
                sum = sum+x;
                x++;
            }
            if (sum==N[i]){
                System.out.println("YES");
            }
            else{
                System.out.println("NO");
            }
            sum=0;  
            x=1;
        }
        
        scanner.close();
        
    }

Answer 1

数学在这里起作用。您可以使用二次方程求解。前N个自然数之和为n*(n+1)/2。所以基本上

⇾ 1 + 2 + 3 + …. N =  S
⇾ (N * (N + 1)) /  2 = S
⇾ N * (N + 1) = 2 * S
⇾ N2  + N  – 2 * S = 0

我们知道你的 s 所以只要解二次方程就可以了。像

import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int sum =0;
        int x=1;
        int Q = scanner.nextInt();
        int []N=new int [Q];
        for (int i = 0 ; i<Q;i++){
            N [i]= scanner.nextInt();

            // Solution of Quadratic Equation
            double k = (-1.0 + Math.sqrt(1 + 8 * N[i])) / 2;
           
            // Condition to check if the
            // solution is a integer
            if (Math.ceil(k) == Math.floor(k))
              System.out.println("YES");
            else
              System.out.println("NO");
        }
        
    }

如果您有兴趣，此页面也有二进制搜索解决方案。 https://www.geeksforgeeks.org/find-given-number-sum-first-n-natural-numbers/

如何检查一个非常大的数字是否是 1 的连续和？

How to check if a really big number is a continuous sum from 1?

java

arrays

sum