#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; using uint = unsigned int; #define LL __int128 #define ld long double #define INF 2251799813685248 #define rep(i, n) for (ll i = 0; i < (n); ++i) #define reps(i, l, r) for(ll i = (l); i < (r); ++i) #define foreach(c, A) for(auto c:(A)) #define vall(A) (A).begin(),(A).end() #define vrall(A) (A).rbegin(),(A).rend() #define slice(A, l, r) next((A).begin(), (l)), next((A).begin(), (r)) #define vin(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cin >> (A)[iiii];} #define vout(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cout << (A)[iiii] << " \n"[iiii == szszszsz-1];} #define vin2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cin >> (A)[iiii][jjjj];}} #define vout2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cout << (A)[iiii][jjjj] << " \n"[jjjj==(A)[iiii].size()-1];}} #define encode(i,j) (((i))<<32)+(j) #define decode(v,w) ((w) ? (v)%4294967296 : (v)>>32) #define vinc(A) for (auto &vvvv : (A)){vvvv++;} #define vdec(A) for (auto &vvvv : (A)){vvvv--;} #define graphin0(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa].push_back(bbbb); (C)[bbbb].push_back(aaaa);} #define graphin1(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa-1].push_back(bbbb-1); (C)[bbbb-1].push_back(aaaa-1);} #define lsegtype(name) name::S, name::F #define lsegarg(name) name::op, name::e,name::comp, name::mapping, name::id vector pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904}; vector pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000}; vector di{0,1,0,-1}; vector dj{1,0,-1,0}; template bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; } template bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; } unsigned int bit_length(ll n){ return n > 0 ? 64 - __builtin_clzll(n) : 0;} template T sum(vector A){ T res = 0; for (size_t i=0;i 0){ if ((n & 1) == 1){ ans *= p; ans %= m; } n >>= 1; p *= p; p %= m; } return (ll)ans; } // Injecting boilerplate.hpp <- _lib/divsor.hpp // Skipping already injected boilerplate.hpp // Skipping already injected boilerplate.hpp // Skipping already injected boilerplate.hpp // Skipping already injected boilerplate.hpp // Skipping already injected boilerplate.hpp template inline constexpr bool always_false_v = false; template inline int bit_length(T n) { if constexpr (std::is_same_v) { return n > 0 ? 32 - __builtin_clz(n) : 0; } else if constexpr (std::is_same_v) { return n > 0 ? 32 - __builtin_clz(n) : 0; } else if constexpr (std::is_same_v) { return n > 0 ? 64 - __builtin_clzll(n) : 0; } else if constexpr (std::is_same_v) { return n > 0 ? 64 - __builtin_clzll(n) : 0; } else { static_assert(always_false_v, "bit_length: unsupported type"); return 0; } } template inline int bit_count(T n) { if constexpr (std::is_same_v) { return __builtin_popcount(n); } else if constexpr (std::is_same_v) { return __builtin_popcount(n); } else if constexpr (std::is_same_v) { return __builtin_popcountll(n); } else if constexpr (std::is_same_v) { return __builtin_popcountll(n); } else { static_assert(always_false_v, "bit_count: unsupported type"); return 0; } } // Injecting bit.hpp <- _lib/MillerRabin.hpp bool MillerRabin(ll N, vector arr) { int s = bit_length((N - 1) & (-(N - 1))) - 1; ll d = (N - 1) >> s; for (auto a : arr) { if (N <= a) { return true; } ll x = powll(a, d, N); int t; if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = __int128_t(x) * x % N; } if (t == s) return false; } } return true; } // Injecting MillerRabin.hpp <- _lib/isprime.hpp constexpr bool isprime(ll N) { if (N <= 1) { return false; } if (N == 2) { return true; } if (N % 2 == 0) { return false; } if (N < 4759123141LL) { return MillerRabin(N, {2, 7, 61}); } else { return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } } // Injecting isprime.hpp <- _lib/Pollards_rho.hpp ll find_factor(ll n){ // n should be composite number. if (n % 2 == 0){ return 2; } for(int c=1;;c++){ auto f = [&](ll x){ return (__int128_t(x) * x + c) % n; }; ll x = 2, y = 2, d = 1; while (d == 1){ x = f(x); y = f(f(y)); d = gcd(abs(x - y), n); } if (d != n){ return d; } } } void Pollards_rho_Enumerater(ll n, vector& res){ if (isprime(n)){ res.push_back(n); } else { ll g = find_factor(n); Pollards_rho_Enumerater(g, res); Pollards_rho_Enumerater(n/g, res); } } vector Pollards_rho(ll n){ vector res; Pollards_rho_Enumerater(n, res); sort(vall(res)); return res; } // Injecting Pollards_rho.hpp <- _lib/factorize.hpp vector factorize_primitive(ll n){ vector factors; for (ll i = 2; i * i <= n; i++) { while (n % i == 0) { n /= i; factors.push_back(i); } } if (n > 1) { factors.push_back(n); } return factors; } vector factorize(ll n){ if (n <= 1000000){ return factorize_primitive(n); } else { return Pollards_rho(n); } } // Injecting factorize.hpp <- _lib/divsor.hpp // Skipping already injected boilerplate.hpp template unordered_map Counter(vector arr){ unordered_map res; for(auto& x: arr){ res[x] += 1; } return res; } // Injecting Counter.hpp <- _lib/divsor.hpp // Skipping already injected boilerplate.hpp // Skipping already injected factorize.hpp // Skipping already injected Counter.hpp ll count_divsor(ll n){ auto factors = factorize(n); auto dict = Counter(factors); ll ans = 1; for (auto [_, e]:dict){ ans *= (e+1); } return ans; } ll count_divsor(unordered_map& dict){ ll ans = 1; for (auto [_, e]:dict){ ans *= (e+1); } return ans; } // Injecting count_divsor.hpp <- _lib/divsor.hpp // 整数 n を入れられたとき、それを勝手に素因数分解して約数一覧を返す vector divsors(ll n){ auto factors = factorize(n); auto dict = Counter(factors); vector ds(1,1); for(auto [p,e] : dict){ int pre_sz = ds.size(); for (int i = 0;i divsors(unordered_map dict){ vector ds(1,1); for(auto [p,e] : dict){ int pre_sz = ds.size(); for (int i = 0;i> a; auto x = divsors(a); cout << sum(x) << endl; }