#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b= (ll)M); } ull modpow(ull b, ull e, ull mod) { ull ans = 1; for (; e; b = modmul(b, b, mod), e /= 2) if (e & 1) ans = modmul(ans, b, mod); return ans; } /** * Author: chilli, SJTU, pajenegod * Date: 2020-03-04 * License: CC0 * Source: own * Description: Pollard-rho randomized factorization algorithm. Returns prime * factors of a number, in arbitrary order (e.g. 2299 -> \{11, 19, 11\}). * Time: $O(n^{1/4})$, less for numbers with small factors. * Status: stress-tested * * Details: This implementation uses the improvement described here * (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants…), where * one can accumulate gcd calls by some factor (40 chosen here through * exhaustive testing). This improves performance by approximately 6-10x * depending on the inputs and speed of gcd. Benchmark found here: * (https://ideone.com/nGGD9T) * * GCD can be improved by a factor of 1.75x using Binary GCD * (https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/…). * However, with the gcd accumulation the bottleneck moves from the gcd calls * to the modmul. As GCD only constitutes ~12% of runtime, speeding it up * doesn't matter so much. * * This code can probably be sped up by using a faster mod mul - potentially * montgomery reduction on 128 bit integers. * Alternatively, one can use a quadratic sieve for an asymptotic improvement, * which starts being faster in practice around 1e13. * * Brent's cycle finding algorithm was tested, but doesn't reduce modmul calls * significantly. * * Subtle implementation notes: * - we operate on residues in [1, n]; modmul can be proven to work for those * - prd starts off as 2 to handle the case n = 4; it's harmless for other n * since we're guaranteed that n > 2. (Pollard rho has problems with prime * powers in general, but all larger ones happen to work.) * - t starts off as 30 to make the first gcd check come earlier, as an * optimization for small numbers. */ #pragma once /** * Author: chilli, c1729, Simon Lindholm * Date: 2019-03-28 * License: CC0 * Source: Wikipedia, https://miller-rabin.appspot.com * Description: Deterministic Miller-Rabin primality test. * Guaranteed to work for numbers up to $7 \cdot 10^{18}$; for larger numbers, use Python and extend A randomly. * Time: 7 times the complexity of $a^b \mod c$. * Status: Stress-tested */ #pragma once bool isPrime(ull n) { if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3; ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, s = __builtin_ctzll(n-1), d = n >> s; for (ull a : A) { // ^ count trailing zeroes ull p = modpow(a%n, d, n), i = s; while (p != 1 && p != n - 1 && a % n && i--) p = modmul(p, p, n); if (p != n-1 && i != s) return 0; } return 1; } ull pollard(ull n) { auto f = [n](ull x) { return modmul(x, x, n) + 1; }; ull x = 0, y = 0, t = 30, prd = 2, i = 1, q; while (t++ % 40 || __gcd(prd, n) == 1) { if (x == y) x = ++i, y = f(x); if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q; x = f(x), y = f(f(y)); } return __gcd(prd, n); } vector factor(ull n) { if (n == 1) return {}; if (isPrime(n)) return {n}; ull x = pollard(n); auto l = factor(x), r = factor(n / x); l.insert(l.end(), all(r)); return l; } ll ans; vector> S; vector T; void DFS(int u,ll x){ if(u==si(S)){ T.push_back(x); return; } for(int q=0;q<=S[u].se;q++){ DFS(u+1,x); x*=S[u].fi; } } void solve(ll la,ll rem){ if(rem==1){ ans++; return; } if(la>rem) return; if(la==rem){ ans++; return; } if(rem%la) return; if((rem/la)%la){ if(rem%la==0) ans++; return; } auto it=lower_bound(all(T),la); while(it!=T.end()){ ll x=*it; if(x%la==0&&rem%x==0){ solve(x,rem/x); } if(x>rem) return; it++; } } int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); ll N;cin>>N; auto fa=factor(N); //return 0; map MA; for(ll x:fa) MA[x]++; for(auto [a,b]:MA) S.push_back(mp(a,b)); DFS(0,1); sort(all(T)); for(ll x:T){ if(x==1) continue; solve(x,N/x); } cout<