(已修改)

枚举

gcd=1肯定是最差选择因为任何一个gcd大于1的值都要比gcd1的选择要优(gcd=1的最优也就是2*x-1)，那么可以枚举x的所有因数，找到该最大因数的倍数小于x的情况，取所有情况的最大值即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
int get(int x,int y){
	int d=(y-1)/x;
	return (x*d+y)*(x);
}
signed main() {
	int t;
	cin>>t;
	while(t--){
		int x;
		cin>>x;
		int ans=2*x-1;
		for(int i=2;i*i<=x;i++){
			if(x%i==0){
				ans=max(ans,get(i,x));
				int y=x/i;
				ans=max(ans,get(y,x));
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

python

def get(x, y):
    d = (y - 1) // x
    return (x * d + y) * x

# 读取测试次数
t = int(input())

for _ in range(t):
    x = int(input())
    ans = 2 * x - 1
    i = 2
    while i * i <= x:
        if x % i == 0:
            ans = max(ans, get(i, x))
            y = x // i
            ans = max(ans, get(y, x))
        i += 1
    print(ans)

java

import java.util.Scanner;

public class Main {

    // 计算get函数
    static long get(long x, long y) {
        long d = (y - 1) / x;
        return (x * d + y) * x;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();  // 读取测试次数
        while (t-- > 0) {
            long x = sc.nextLong();
            long ans = 2 * x - 1;

            for (long i = 2; i * i <= x; i++) {
                if (x % i == 0) {
                    ans = Math.max(ans, get(i, x));
                    long y = x / i;
                    ans = Math.max(ans, get(y, x));
                }
            }

            System.out.println(ans);
        }
    }
}

题目内容

小红有一个正整数$x$，他希望你找到一个满足$1≤y<x$的正整数$y$，使得:$(x +y)×gcd(x,y)$ 的值尽可能大，请你帮他求出这个最大值吧。 $gcd(x,y)$表示$x$和$y$的最大公约数，例如:$gcd(4,6)=2$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^3$)代表数据组数，每组测试数据描述如下：

在一行上输入一个正整数$x$($2 ≤x≤10^9$)，表示小红询问的$x$。

输出描述

对于每组测试数据，输出包含一行一个正整数，表示$(x+y)×gcd(x,y)$的最大值。

样例1

输入

3 
3
6
5

输出

5
27
9