题目描述

小王是一个喜欢健身的人，他每天都会围着一个n*n的场地外侧跑步。他是一个有强迫症的人，每跑n+1个单位长度，他就要在地上做一个标记。当他在一个点重复标记的时候，他就会结束当天的锻炼。显然当n一定时，他每天打标记的数量也是一-定的。请你计算出来他每天要打多少个标记(最后一次重复标记也要计数)。

输入格式
第一行包含1个正整数t,表示询问的数量。
第二行包含t个整数，中间用空格隔开，每个整数表示一个询问所给出的n。

输出格式
输出共t行。
每行包含一个正整数，中第i行的整数表示第i个询问的答案。

数据范围
1 <= t <= 10000
1 <= n <= 1000

样例

输入样例
2
4 8

输出样例
17
33

Java 代码

public class Problem1 {
    public static void main(String[] args) {
        Problem1 problem1 = new Problem1();
        problem1.get();
    }


    public void get(){
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        while(count > 0){
            count--;
            int n = sc.nextInt();
            System.out.println(4 * n / gcd(4*n, n+1) + 1);
        }
    }


    private int gcd(int a, int b) {
        if (a < b){
          int temp = a;
          a = b;
          b = temp;
        }
        return b == 0? a: gcd(b, a % b);
    }

}

时间复杂度

o(10000* log(10000))