DiviDuelo

标签：std return factors int number DiviDuelo vector

https://codeforces.com/gym/105053/problem/D
我发现了p^alpha = N ,alpha % 2 != 0 以及 pq = N,(p，q为素数)的情况下先手玩家有必胜策略，然而我不知道如何用O(sqrt(N))的算法分解出上面的东西
`#include<bits/stdc++.h>

using namespace std;
std::vector factorize(int n) {
std::vector factors;

for (int i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
        factors.push_back(i);
        n /= i;
    }
}

if (n > 1) {
    factors.push_back(n);
}

return factors;

}

bool hasWinningStrategy(int n) {
std::vector factors = factorize(n);
int distinctPrimes = 0;

for (int i = 0; i < factors.size(); ++i) {
    if (i == 0 || factors[i] != factors[i - 1]) {
        distinctPrimes++;
    }
}

if (distinctPrimes == 1 && factors.size() % 2 == 0) {
    return false;
}

return true;

}

int main() {
int number;
std::cin >> number;
if (number == 1) {
cout << "N" << endl;
return 0;
}

bool hasStrategy = hasWinningStrategy(number);

if (hasStrategy) {
    std::cout << "Y" << std::endl;
} else {
    std::cout << "N" << std::endl;
}

return 0;

}
`

标签：std,return,factors,int,number,DiviDuelo,vector
From： https://www.cnblogs.com/peterzh/p/18132852