Question

Câu 6. Tích chính phương – tichcp.* Cho trước số nguyên dương N (0< N≤ 10¹²). Yêu cầu: Tìm số nguyên dương K (K≥1) nhỏ nhất sao cho tích của K và N là một số chính phương. Dữ liệu vào: một số nguyên dương N. Dữ liệu ra: ghi số nguyên K tìm được. Ví dụ: input output 3 3 18 2 Ràng buộc

-Có 50% số test ứng với 𝑁 ≤ 10

-Có 50% số test ứng với 𝑁 ≤ 10¹²

Answer 1

#include <bits/stdc++.h>

using namespace std;
long long a[1000006];
long long n;
int main()
{
    for(int i=1;i<=1000006;i++){
        a[i]=i*i;
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        if(a[i]%n==0){cout<<a[i]/n;break;}
    }
    return 0;
}