I will be very puzzled if that problem has a solution with logarithmic running time. And I hope that is sufficient. But if the prime factorization of k is known maybe I can solve it in .

Consider the prime factorization of k: k = p₁^k₁p₂^k₂... p_r^k_r , and we want to find a number of representations looks like a^b = (p₁^a₁p₂^a₂... p_r^a_r)^b = p₁^k₁p₂^k₂... p_r^k_r .

Let g = gcd(k₁, k₂, ... , k_r) . All of valid representations looks like (p₁^k₁ / dp₂^k₂ / d... p_r^k_r / d)^d , where d is any divisor of g.

To satisfy 1 ≤ a ≤ n constraint we find min d such that (p₁^k₁ / dp₂^k₂ / d... p_r^k_r / d) ≤ n through binary search. It`s minimal valid d. Constraint 1 ≤ b ≤ m gives us maximal valid value of d. And answer is d_max - d_min + 1 .

Can you please share the problem link?

We need to find number of pairs (A, B) such that their XOR is K.
Consider binary representations of K — if some bit is 1 then respective bits in A and B must be different, and if bit is 0 then they need to be same.
Now we can represent N and M in binary and then solve it with DP[prefix][flag1][flag2].
prefix — how many bits are already placed in A and B.
flag1 — 0 if current prefix of A is same as prefix of N and 1 if it is less. flag2 is same as flag1 but for B.