Official Editorial

Implementation

Time Complexity: O(Nlog⁡2NN)\mathcal{O}(N\log ^2N \sqrt N)

C++

#include <bits/stdc++.h>
using namespace std;


using ll = long long;
using pi = pair<int, int>;


int exponent;


/**
 * We can define a prime factorization pair as the following:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum