Power Board
Contest: Codeforces Round 774 (Div. 2)
Difficulty rating: 2200
Tags: brute force, dp, math, number theory

You have a rectangular board of size $$$n\times m$$$ ($$$n$$$ rows, $$$m$$$ columns). The $$$n$$$ rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the $$$m$$$ columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

The cell at the intersection of row $$$i$$$ and column $$$j$$$ contains the number $$$i^j$$$ ($$$i$$$ raised to the power of $$$j$$$). For example, if $$$n=3$$$ and $$$m=3$$$ the board is as follows:

Find the number of distinct integers written on the board.

Input format:
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^6$$$) — the number of rows and columns of the board.

Output format:
Print one integer, the number of distinct integers on the board.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
The statement shows the board for the first test case. In this case there are $$$7$$$ distinct integers: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$8$$$, $$$9$$$, and $$$27$$$.

In the second test case, the board is as follows:

There are $$$5$$$ distinct numbers: $$$1$$$, $$$2$$$, $$$4$$$, $$$8$$$ and $$$16$$$.

In the third test case, the board is as follows:

There are $$$6$$$ distinct numbers: $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$9$$$ and $$$16$$$.

Example input:
3 3

Example output:
7

Example input:
2 4

Example output:
5

Editorial:
It is easy to see that the first row only contains the number $$$1$$$ and that this number doesn't appear anywhere else on the board.
We say that an integer is a perfect power if it can be represented as $$$x^a$$$ where $$$x$$$ and $$$a$$$ are positive integers and $$$a>1$$$. For each positive integer $$$x$$$ which is not a perfect power, we call $$$R(x)$$$ to the set of all numbers which appear in rows $$$x, x^2, x^3, \ldots$$$.
Claim: If $$$x\neq y$$$ are not perfect powers, then $$$R(x)$$$ and $$$R(y)$$$ have no elements in common. Proof: Suppose there is a common element, then there exist positive integers $$$a,b$$$ such that $$$x^a=y^b$$$. This is the same as $$$\displaystyle x=y^{\frac{b}{a}}$$$. Because $$$y$$$ is not a perfect power, $$$\displaystyle \frac{b}{a}$$$ has to be a positive integer. If $$$\displaystyle \frac{b}{a}=1$$$ then $$$x=y$$$, which cannot happen. So then $$$\displaystyle \frac{b}{a}>1$$$, which cannot happen as $$$x$$$ is not a perfect power. Thus, this common element cannot exist.
Based on the observation above, for each not perfect power $$$x$$$ we can compute the size of $$$R(x)$$$ independently and then sum the results. For a fixed $$$x$$$, let $$$k$$$ be the number of rows that start with a power of $$$x$$$. Then $$$R(x)$$$ contains all numbers of the form $$$x^{i\cdot j}$$$ where $$$1\leq i\leq k$$$ and $$$1\leq j\leq m$$$. But, the size of this set is the same as the size of the set containing all numbers of the form $$$i\cdot j$$$ where $$$1\leq i\leq k$$$ and $$$1\leq j\leq m$$$. Note that the number of elements in this set does not depend on $$$x$$$, it just depends on $$$k$$$.
Thus, the size of $$$R(x)$$$ is uniquely determined by the value of $$$k$$$. As $$$x^k\leq n$$$, then we have that $$$k\leq \text{log}(n)$$$. Then, for each $$$k=1,2,\ldots,\lfloor\text{log}(n)\rfloor$$$ we just need to compute the number of distinct elements of the form $$$i\cdot j$$$ where $$$1\leq i\leq k$$$ and $$$1\leq j\leq m$$$. We can do this using an array of length $$$m \cdot \text{log}(n)$$$, and at the $$$i$$$-th step (for $$$i=1,2,\ldots,\lfloor\text{log}(n)\rfloor$$$) we mark the numbers $$$i,2i,\ldots, mi$$$ as visited in the array, and add one to the value we are computing for each number that was not visited before. After the $$$i$$$-th step we have computed this value for $$$k=i$$$.
So, to solve the problem it is enough to compute for each not perfect power $$$x$$$, how many rows in the matrix start with a power of $$$x$$$ and using the values we calculated in the last paragraph we can know how many distinct numbers are there in $$$R(x)$$$.
Intended complexity: $$$\mathcal{O}(m\:\text{log}\:n + n)$$$