Java Sigma 方程求解 sigma(i=1 到 k)((-1)^i+1)(i)(i+1) 长值超时

Question

Getting timedout error while calculating the value of sigma notation sigma(i=1 to k)((-1)^i+1)(i)(i+1) for very long values example :10^8 .Can any one guide me where I am doing wrong

import java.io.*;
import java.util.*;


public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine().trim());
        for(int t_i=0; t_i<T; t_i++)
        {
            int params1 = Integer.parseInt(br.readLine().trim());

            long out_ = maxValueX(params1);
            System.out.println(out_);
            System.out.println("");
         }

         wr.close();
         br.close();
    }
    static long maxValueX(long params1){
        long sum=0;
       for(long i=1;i<=params1;i++){
           sum=(long)Math.pow(-1,i+1)*i*(i+1)+sum;
       }
       return sum;

    }
}

Answer 1

诀窍是简化 sigma 表达式。如果 params1 是偶数：

1*2 - 2*3 + 3*4 - 4*5 + 5*6 - 6*7 + ... =
(1*2 - 2*3) + (3*4 - 4*5) + (5*6 - 6*7) + ... =
2*(1-3) + 4*(3-5) + 6*(5-7) + ... =
-2*2 + -2*4 + -2*6 + ... =
-2*2*(1 + 2 + 3 + ...)

现在，括号中的项有一个封闭式公式，因此您甚至不需要迭代计算它：https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

这种方法也适用于奇数 params1，只是最后会有一个额外的项需要考虑在内。

通过一些进一步的代数运算（留作 reader 的练习），可以推导出一个适用于奇数和偶数参数的公式。在伪代码中（恰好有效 Python）：

def linear_time(n):
  return sum((-1)**(i+1)*i*(i+1) for i in range(1, n+1))

def constant_time(n):
  return (-1)**n * (-n*n//2 - n)

for n in (100, 101, 120, 100000, 1297981):
  print linear_time(n), constant_time(n)

（求幂只是计算符号的惰性快捷方式；我们实际上不需要为此计算指数。）

Java Sigma 方程求解 sigma(i=1 到 k)((-1)^i+1)(i)(i+1) 长值超时

Java Sigma Equation Solving sigma(i=1 to k)((-1)^i+1)(i)(i+1) Timedout for long values

java

induction