AcWing 3815. 最大约数

原题链接

题目描述

一个正整数 $x$ 被称为一个可爱数当且仅当不存在任何正整数 $a>1$ 满足 $a^2$ 是 $x$ 的约数。

给定一个正整数 $n$，请计算并输出 $n$ 的所有约数中，属于可爱数的最大约数。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含一个整数 $n$。

输出格式

每组数据输出一行结果。

数据范围

$1≤T≤10$,
$1≤n≤10^{12}$

样例

输入样例：

2
10
12

输出样例：

10
6

思路

任意正整数 $m$ 都可以分解质因数成 $m = p^{\alpha_1}_1p^{\alpha_2}_2 \cdots p^{\alpha_k}_k$ 。

可爱数 $a$ 同样的可以被分解质因数成 $a = p^{\beta_1}_1p^{\beta_2}_2 \cdots p^{\beta_k}_k$ ，只不过，$0 \le \beta_i \le 1$ 。

对于 $n$ 的任意约数 $d$ ，如果 $d$ 是可爱数，同样可以被分解质因数：$d = p^{\beta_1}_1p^{\beta_2}_2…p^{\beta_k}_k$ ，且 $0 \le \beta_i \le 1$ 。

要使得 $d$ 尽量大，则 $\beta_i = 1$ 。$d_{max} = p^{\beta_1}_1p^{\beta_2}_2…p^{\beta_k}_k$ ， $\beta_i = 1$ 。

所以给 $n$ 的所有质因数相乘，就是答案。

分解质因数完成后， $n$ 的取值有两种情况：

$$n = \begin{cases} n = 1, & \text{给所有质因子分解完了} \\ n > 1, & \text{还有一个大于 $\sqrt{n}$ 的质因子未被分解} \end{cases}$$

所以结束后，当 $n > 1$ 时，还得乘个 $n$。

代码

C++

#include <iostream>

using namespace std;

typedef long long LL;

int main()
{
    int T;
    cin >> T;
    while ( T-- )
    {
        LL n, res = 1;
        cin >> n;
        for ( int i = 2; i <= n / i; i ++ ) 
            if ( n % i == 0 )
            {
                res *= i;
                while ( n % i == 0 ) n /= i;
            }
        res *= n;
        cout << res << endl;
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    static Scanner in = new Scanner(System.in);
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            long n = in.nextLong(), res = 1;
            for ( int i = 2; i <= n / i; i ++ )
                if ( n % i == 0 ) 
                {
                    res *= i;
                    while ( n % i == 0 ) n /= i;
                }
            res *= n;
            System.out.printf("%d\n", res);
        }
    }
    
}