[每 日 一 题]Acwing 3815. 最大约数

前言

数论基础 重温了一遍

本来以为这题 起码On 做不了 然后就一只在考虑 没想到是数论

这么一优化下来 直接O √n

nb 666

收获

因数 只有 1 和 质数

思路

因此 我们知道 如果不存在一个 a^2的 约数 即所有的a1 ,a2 ,a3 … 都要 = 0或者1

因为题中要求是最大 所以 指数需要全部为1

那么我们只需要 枚举出所有的质因数 相乘 即得答案 ’

CODE

#include 
using namespace std;
using  ll  = long long ;

void solve()
{
    ll n;
    cin>> n ;

    ll res = 1;
    for(ll i =  2 ; i 1)res*=n;
    cout