#include #include int cmp_ll (const void *ap, const void *bp) { long long a = *(long long *)ap; long long b = *(long long *)bp; if (a < b) { return -1; } if (a > b) { return 1; } return 0; } int gcd (int a, int b) { if (a <= 0 || b <= 0) { return a+b; } if (a%b == 0) { return b; } return gcd(b, a%b); } int main () { int p = 0; int q = 0; int res = 0; int ans_cnt = 0; int tmp_cnt = 0; long long ans[2000000][2] = {}; int d = 0; int div[1500] = {}; int div_cnt = 0; int b[1500] = {}; int tmp = 0; int primes[32] = {}; int primes_cnt = 0; res = scanf("%d", &p); res = scanf("%d", &q); d = gcd(p, q); p /= d; q /= d; tmp = q; for (int i = 1; i*i <= q; i++) { if (q%i == 0) { div[div_cnt] = i; div_cnt++; if (q/i != i) { div[div_cnt] = q/i; div_cnt++; } } } tmp = q; for (int i = 2; i*i <= q; i++) { if (tmp%i == 0) { primes[primes_cnt] = i; primes_cnt++; while (tmp%i == 0) { tmp /= i; } } } if (tmp > 1) { primes[primes_cnt] = tmp; primes_cnt++; } for (int i = 0; i < div_cnt; i++) { for (int j = 0; j < primes_cnt; j++) { if (div[i]%primes[j] == 0) { b[i] |= (1<