#pragma once
#include <ostream>
#include <vector>
#include <map>
#include <cmath>

//1000内的质数表
unsigned int prime_num[168] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 };

//存储结果（为了防范数据被修改和方便输出）
struct Root
{
	unsigned int coefficient;   //根号外系数
	unsigned int radicand;      //根号内被开方数
	friend std::ostream& operator << (std::ostream&, Root&);
};

std::ostream& operator << (std::ostream& output, Root& r) {
    if (r.radicand == 1) {          //当能直接开方时，结果不输出r1
        std::cout << r.coefficient;
        return output;
    }
    if (r.coefficient == 1) std::cout << 'r' << r.radicand;     //当系数为1时，不输出系数
	else output << r.coefficient << 'r' << r.radicand;
	return output;
}

Root sqrt(unsigned int x) {
    //判断是否可直接开方，若能直接返回结果
    double y = std::sqrt(x);
    if (static_cast<double>(static_cast<int>(y)) == y) {
        return Root({ static_cast<unsigned int>(y), 1 });
    }
    //对被开方数分解质因数
    std::vector<unsigned int> primeFactor;
    for (unsigned int* i = prime_num; i <= &prime_num[167]; ) {
        if (*i > x) break;
        if (x % *i == 0) { primeFactor.push_back(*i); x /= *i;  continue; }
        if (x == 1) break;
        ++i;
    }
    //将偶数次幂提出开方
    std::map<unsigned int, unsigned int> primeFactorAndTimes, coefficientPart;
    for (const unsigned int& i : primeFactor) primeFactorAndTimes.insert({ i,0 });
    for (const unsigned int& i : primeFactor) ++primeFactorAndTimes[i];
    std::vector<unsigned int> erase;   //删除被开方数中的可开方部分
    for (const auto& [factor, times] : primeFactorAndTimes) {
        if (times > 1) {
            if (times % 2 == 0) {
                coefficientPart.insert({ factor,(times / 2) });
                erase.push_back(factor);
            }
            else {
                coefficientPart.insert({ factor,((times - 1) / 2) });
                primeFactorAndTimes[factor] = 1;
            }
        }
    }
    for (const auto& i : erase) primeFactorAndTimes.erase(i); //循环内部删除元素会导致迭代器失效
    //求根号内外的结果
    unsigned int  coefficient = 1, radicand = 1;
    for (const auto& [base, index] : coefficientPart) coefficient *= static_cast<int>(std::pow(base, index));
    for (const auto& [base, index] : primeFactorAndTimes) radicand *= static_cast<int>(std::pow(base, index));
    return Root({ coefficient, radicand });
}