#include #include #include #include #include #include #include #include #include #include #include #include #define rf freopen("in.in", "r", stdin) #define wf freopen("out.out", "w", stdout) #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i) using namespace std; const int mx = 1e5+10, mod = 1e9+7; long long int n, m, total_ans = 0; vector prime_f, prime_c; vector< pair > g[mx]; int vis[mx]; void prime_factorize() { int num = m; for(int i = 2; i<=num; ++i) { if(num%i == 0) { int cnt = 0; while(num % i == 0) cnt++, num/=i; prime_f.push_back(i); prime_c.push_back(cnt); } } } vector prime_counts_in_num(int number) { vector ret; for(int i = 0; i 0) cnt++, number/= prime_f[i]; ret.push_back(cnt); } return ret; } void count_it(map< vector, int> a, map< vector, int> b) { map< vector, int>::iterator it, iter; for(it = a.begin(); it!= a.end(); ++it) { map< vector, int>::iterator iter = b.begin(); for(iter = b.begin(); iter!= b.end(); ++iter) { bool check = true; for(int i = 0; ifirst[i]) + (iter->first[i]) < prime_c[i]) { check = false; break; } } if(check) total_ans += (it->second) * (iter->second); } } } map< vector, int> add_edge(map< vector, int> base, int number) { vector pinn = prime_counts_in_num(number); map< vector, int>::iterator it; map< vector, int> new_set; for(it = base.begin(); it!= base.end(); ++it) { vector new_entry; for(int i = 0; ifirst[i]+pinn[i])); } new_set[new_entry]+=it->second; } return new_set; } void merge(map< vector, int> &a, map< vector, int> b) { map< vector, int> new_set; map< vector, int>::iterator it, iter; for(it = b.begin(); it!= b.end(); ++it) { a[it->first] += it->second; } } map< vector, int> dfs(int u) { map< vector, int> cur; vector new_entry; for(int i = 0; i< prime_f.size(); ++i) new_entry.push_back(0); cur[new_entry] = 1; vis[u] = 1; for(int i = 0; i, int> child = dfs(v); child = add_edge(child, dis); count_it(cur, child); merge(cur, child); } return cur; } int main() { //rf;// wf; scanf("%lld %lld", &n, &m); prime_factorize(); for(int i = 1; i