CSES - Shared codeLink to this code:
https://cses.fi/paste/de0fc8791c1df04fde3d6/#include "bits/stdc++.h" // template by Benq
using namespace std; // Debug template credit: Benq, ramchandra
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using ull = unsigned ll;
using pi = pair<ll, ll>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using pld = pair<ld, ld>;
using vi = vector<ll>;
using vd = vector<db>;
using vl = vector<ll>;
using vld = vector<ld>;
using vs = vector<str>;
using vb = vector<bool>;
using vc = vector<char>;
using vpi = vector<pl>;
using vpl = vector<pl>;
using vpd = vector<pd>;
using vvi = vector<vl>;
using vvl = vector<vl>;
using vvc = vector<vc>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define si(a) ((int)(a).size())
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define rs resize
#define ins insert
#define nl "\n"
#define sor(a) sort(all(a))
#define res(a, n) a.rs(n); re(a)
#define int long long
#define sort_by(x, y) sort(all(x), [&](const auto& a, const auto& b) { return y; } )
#define rep(i, a, b) for(auto i = (a); i < (b); ++i)
#define rop(i, a) rep(i, 0, a)
#define per(i, a, b) for(auto i = (b) - 1; i >= (a); --i)
#define por(i, a) per(i, 0, a)
#define trav(i, a) for (auto& i: a)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> void uni(vector<T>& v) { sor(v); v.erase(unique(all(v)), end(v)); }
int cdiv(const ll& a, const ll& b) { return a / b + ((a ^ b) > 0 && a % b); } // (a / b) rounded up
int fdiv(const ll& a, const ll& b) { return a / b - ((a ^ b) < 0 && a % b); } // (a / b) rounded down
int fstTrue(function<bool(int)> f, int lo, int hi) { for(hi++; lo < hi;) { int mid = fdiv((lo + hi), 2); f(mid) ? hi = mid : lo = mid + 1; } return lo; }
int lstTrue(function<bool(int)> f, int lo, int hi) { for(lo--; lo < hi;) { int mid = fdiv((lo + hi + 1), 2); f(mid) ? lo = mid : hi = mid - 1; } return lo; }
int power(ll a, ll b, ll c) { ll res = 1; a %= c; while(b > 0) { if(b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
int power(ll a, ll b) { ll res = 1; while(b > 0) { if(b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
ull modMul(ull a, ull b, const ull mod) { ll ret = a * b - mod * (ull)((ld)a * b / mod); return ret + ((ret < 0) - (ret >= (ll)mod)) * mod; }
ull modPow(ull a, ull b, const ull mod) { if(b == 0) { return 1; } ull res = modPow(a, b / 2, mod); res = modMul(res, res, mod); return b & 1 ? modMul(res, a, mod) : res; }
bool prime(ull n) { if(n < 2 || n % 6 % 4 != 1) { return n - 2 < 2; } ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, s = __builtin_ctzll(n - 1), d = n >> s; trav(i, A) { ull p = modPow(i, d, n), a = s; while(p != 1 && p != n - 1 && i % n && a--) { p = modMul(p, p, n); } if(p != n - 1 && a != s) { return false; } } return true; }
int pct(int x) { x = (x & 0x5555555555555555LL) + ((x >> 1) & 0x5555555555555555LL); x = (x & 0x3333333333333333LL) + ((x >> 2) & 0x3333333333333333LL); x = (x & 0x0F0F0F0F0F0F0F0FLL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FLL); return (x * 0x0101010101010101LL) >> 56; }
// uni: O(nlog(n)), cdiv: O(1), fdiv: O(1), fstTrue: O(log(hi - lo)), lstTrue: O(log(hi - lo)), gcd: O(log(min(a, b))), lcm: O(log(min(a, b))), power: O(log(b)), prime: O(sqrt(a)), pct: O(1)
// TO_STRING
#define ts to_string
string ts(char c) { return string(1, c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) { stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) { string res = "{"; for(int i = 0; i < si(v); i++) { res += char('0' + v[i]); } res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) { string res = ""; for(int i = 0; i < (ll)SZ; i++) { res += char('0' + b[i]); } return res; }
template<class A, class B> string ts(pair<A, B> p) { return "(" + ts(p.f) + ", " + ts(p.s) + ")"; }
template<class T> string ts(T v) { bool fst = 1; string res = "{"; for(const auto& x: v) { if(!fst) { res += ", "; } fst = 0; res += ts(x); } res += "}"; return res; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << ts(h); if(sizeof...(t)) { cerr << ", "; } DBG(t...); }
void EDBG(string names) { names = names; }
template<class H, class... T> void EDBG(string names, H h, T... t) { auto pos = names.find(','); auto first_name = names.substr(0, pos); auto rest = names.substr(pos + 1); while(rest.front() == ' ') { rest = rest.substr(1); } cerr << "[" << first_name << "]: [" << ts(h) << "]" << nl; EDBG(rest, t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define edbg(...) EDBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 42
#define edbg(...) 7
#endif
// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(20); }
void setIO(string s = "") { unsyncIO(); if(si(s)) { setIn(s + ".in"); setOut(s + ".out"); } }
const int MX = 2e5 + 5;
const long long INF = 1e18;
const long long MOD = 1e9 + 7; // 998244353
const long double PI = acos((ld)-1);
const long double EPS = 1e-18;
namespace NT{
template<typename T>
struct bigger_type{};
template<typename T> using bigger_type_t = typename bigger_type<T>::type;
template<> struct bigger_type<int>{using type = long long;};
template<> struct bigger_type<unsigned int>{using type = unsigned long long;};
//template<> struct bigger_type<int64_t>{using type = __int128;};
//template<> struct bigger_type<uint64_t>{using type = unsigned __int128;};
template<typename int_t = unsigned long long>
struct Mod_Int{
static inline int_t add(int_t const&a, int_t const&b, int_t const&mod){
int_t ret = a+b;
if(ret>=mod) ret-=mod;
return ret;
}
static inline int_t sub(int_t const&a, int_t const&b, int_t const&mod){
return add(a, mod-b);
}
static inline int_t mul(int_t const&a, int_t const&b, int_t const&mod){
uint64_t ret = a * (uint64_t)b - (uint64_t)((long double)a * b / mod - 1.1) * mod;
if(-ret < ret){
ret = mod-1-(-ret-1)%mod;
} else {
ret%=mod;
}
//ret = min(ret, ret+mod);
int64_t out = ret;
/*if(out != a*(__int128) b % mod){
cerr << (long double)a * b / mod << " " << (uint64_t)((long double)a * b / mod - 0.1) << "\n";
cerr << mod << " " << ret << " " << ret+mod << " " << out << " " << (int64_t)(a*(__int128) b % mod) << "\n";
assert(0);
}*/
return out;
//return a*static_cast<bigger_type_t<int_t>>(b)%mod;
}
static inline int_t pow(int_t const&a, int_t const&b, int_t const&mod){
int_t ret = 1;
int_t base = a;
for(int i=0;b>>i;++i){
if((b>>i)&1) ret = mul(ret, base, mod);
base = mul(base, base, mod);
}
return ret;
}
};
template<typename T>
typename enable_if<is_integral<T>::value, bool>::type is_prime(T x){
if(x<T(4)) return x>T(1);
for(T i=2;i*i<=x;++i){
if(x%i == 0) return false;
}
return true;
}
template<typename T>
typename enable_if<is_integral<T>::value, bool>::type miller_rabin_single(T const&x, T base){
if(x<T(4)) return x>T(1);
if(x%2 == 0) return false;
base%=x;
if(base == 0) return true;
T xm1 = x-1;
int j = 1;
T d = xm1/2;
while(d%2 == 0){ // could use __builtin_ctz
d/=2;
++j;
}
T t = Mod_Int<T>::pow(base, d, x);
if(t==T(1) || t==T(xm1)) return true;
for(int k=1;k<j;++k){
t = Mod_Int<T>::mul(t, t, x);
if(t == xm1) return true;
if(t<=1) break;
}
return false;
}
template<typename T>
typename enable_if<is_integral<T>::value, bool>::type miller_rabin_multi(T const&){return true;}
template<typename T, typename... S>
typename enable_if<is_integral<T>::value, bool>::type miller_rabin_multi(T const&x, T const&base, S const&...bases){
if(!miller_rabin_single(x, base)) return false;
return miller_rabin_multi(x, bases...);
}
template<typename T>
typename enable_if<is_integral<T>::value, bool>::type miller_rabin(T const&x){
if(x < 316349281) return miller_rabin_multi(x, T(11000544), T(31481107));
if(x < 4759123141ull) return miller_rabin_multi(x, T(2), T(7), T(61));
return miller_rabin_multi(x, T(2), T(325), T(9375), T(28178), T(450775), T(9780504), T(1795265022));
}
template<typename T>
typename enable_if<is_integral<T>::value, T>::type isqrt(T const&x){
assert(x>=T(0));
T ret = static_cast<T>(sqrtl(x));
while(ret>0 && ret*ret>x) --ret;
while(x-ret*ret>2*ret)
++ret;
return ret;
}
template<typename T>
typename enable_if<is_integral<T>::value, T>::type icbrt(T const&x){
assert(x>=T(0));
T ret = static_cast<T>(cbrt(x));
while(ret>0 && ret*ret*ret>x) --ret;
while(x-ret*ret*ret>3*ret*(ret+1))
++ret;
return ret;
}
/*uint64_t isqrt(unsigned __int128 const&x){
unsigned __int128 ret = sqrtl(x);
while(ret>0 && ret*ret>x) --ret;
while(x-ret*ret>2*ret)
++ret;
return ret;
}*/
vector<uint16_t> saved;
// fast prime factorization from
// https://github.com/radii/msieve
uint64_t squfof_iter_better(uint64_t const&x, uint64_t const&k, uint64_t const&it_max, uint32_t cutoff_div){
if(__gcd((uint64_t)k, x)!=1) return __gcd((uint64_t)k, x);
//cerr << "try: " << x << " " << k << "\n";
saved.clear();
uint64_t scaledn = k*x;
if(scaledn>>62) return 1;
uint32_t sqrtn = isqrt(scaledn);
uint32_t cutoff = isqrt(2*sqrtn)/cutoff_div;
uint32_t q0 = 1;
uint32_t p1 = sqrtn;
uint32_t q1 = scaledn-p1*p1;
if(q1 == 0){
uint64_t factor = __gcd(x, (uint64_t)p1);
return factor==x ? 1:factor;
}
uint32_t multiplier = 2*k;
uint32_t coarse_cutoff = cutoff * multiplier;
//cerr << "at: " << multiplier << "\n";
uint32_t i, j;
uint32_t p0 = 0;
uint32_t sqrtq = 0;
for(i=0;i<it_max;++i){
uint32_t q, bits, tmp;
tmp = sqrtn + p1 - q1;
q = 1;
if (tmp >= q1)
q += tmp / q1;
p0 = q * q1 - p1;
q0 = q0 + (p1 - p0) * q;
if (q1 < coarse_cutoff) {
tmp = q1 / __gcd(q1, multiplier);
if (tmp < cutoff) {
saved.push_back((uint16_t)tmp);
}
}
bits = 0;
tmp = q0;
while(!(tmp & 1)) {
bits++;
tmp >>= 1;
}
if (!(bits & 1) && ((tmp & 7) == 1)) {
sqrtq = (uint32_t)isqrt(q0);
if (sqrtq * sqrtq == q0) {
for(j=0;j<saved.size();++j){
if(saved[j] == sqrtq) break;
}
if(j == saved.size()) break;
//else cerr << "skip " << i << "\n";;
}
}
tmp = sqrtn + p0 - q0;
q = 1;
if (tmp >= q0)
q += tmp / q0;
p1 = q * q0 - p0;
q1 = q1 + (p0 - p1) * q;
if (q0 < coarse_cutoff) {
tmp = q0 / __gcd(q0, multiplier);
if (tmp < cutoff) {
saved.push_back((uint16_t) tmp);
}
}
}
if(sqrtq == 1) { return 1;}
if(i == it_max) { return 1;}
q0 = sqrtq;
p1 = p0 + sqrtq * ((sqrtn - p0) / sqrtq);
q1 = (scaledn - (uint64_t)p1 * (uint64_t)p1) / (uint64_t)q0;
for(j=0;j<it_max;++j) {
uint32_t q, tmp;
tmp = sqrtn + p1 - q1;
q = 1;
if (tmp >= q1)
q += tmp / q1;
p0 = q * q1 - p1;
q0 = q0 + (p1 - p0) * q;
if (p0 == p1) {
q0 = q1;
break;
}
tmp = sqrtn + p0 - q0;
q = 1;
if (tmp >= q0)
q += tmp / q0;
p1 = q * q0 - p0;
q1 = q1 + (p0 - p1) * q;
if (p0 == p1)
break;
}
if(j==it_max) {cerr << "RNG\n"; return 1;} // random fail
uint64_t factor = __gcd((uint64_t)q0, x);
if(factor == x) factor=1;
return factor;
}
uint64_t squfof(uint64_t const&x){
static array<uint32_t, 16> multipliers{1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};
uint64_t cbrt_x = icbrt(x);
if(cbrt_x*cbrt_x*cbrt_x == x) return cbrt_x;
//uint32_t iter_lim = isqrt(isqrt(x))+10;
uint32_t iter_lim = 300;
for(uint32_t iter_fact = 1;iter_fact<20000;iter_fact*=4){
for(uint32_t const&k : multipliers){
if(numeric_limits<uint64_t>::max()/k<=x) continue; //would overflow
uint32_t const it_max = iter_fact*iter_lim;
uint64_t factor = squfof_iter_better(x, k, it_max, 1);
if(factor==1 || factor==x) continue;
return factor;
}
}
cerr << "failed to factor: " << x << "\n";
assert(0);
assert(0);
return 1;
}
template<typename T>
typename enable_if<is_integral<T>::value, vector<T>>::type factorize_brute(T x){
vector<T> ret;
while(x%2 == 0){
x/=2;
ret.push_back(2);
}
for(uint32_t i=3;i*(T)i <= x;i+=2){
while(x%i == 0){
x/=i;
ret.push_back(i);
}
}
if(x>1) ret.push_back(x);
return ret;
}
template<typename T>
typename enable_if<is_integral<T>::value, vector<T>>::type factorize(T x){
//cerr << "factor: " << x << "\n";
vector<T> ret;
const uint32_t trial_limit = 5000;
auto trial = [&](uint32_t const&i){
while(x%i == 0){
x/=i;
ret.push_back(i);
}
};
trial(2);
trial(3);
for(uint32_t i=5, j=2;i<trial_limit && i*i <= x;i+=j, j=6-j){
trial(i);
}
if(x>1){
static stack<T> s;
s.push(x);
while(!s.empty()){
x = s.top(); s.pop();
if(!miller_rabin(x)){
T factor = squfof(x);
if(factor == 1 || factor == x){assert(0); return ret;}
//cerr << x << " -> " << factor << "\n";
s.push(factor);
s.push(x/factor);
} else {
ret.push_back(x);
}
}
}
sort(ret.begin(), ret.end());
return ret;
}
}
struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
template<class T, class H> size_t operator()(pair<T, H> a) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
hash<T> x;
hash<H> y;
return splitmix64(x(a.f) * 37 + y(a.s) + FIXED_RANDOM);
}
};
template<class T, class H> using umap = unordered_map<T, H, custom_hash>;
int n;
int32_t main() {
setIO();
cin >> n;
rop(i, n) {
int a;
cin >> a;
vi hld = NT::factorize(a);
umap<int, int> cnt;
rop(j, si(hld)) {
cnt[hld[j]]++;
}
int ans = 1;
trav(i, cnt) {
ans *= (i.s + 1);
}
cout << ans << nl;
}
}
