Limits
1s, 512 MB

After discovering the famous totient function $\phi(x)$ Euler got so fond of it that he applied it to every number he could find on his table. He played all day with this newly discovered function. Then he went to sleep. He was dreaming about the function too.

In the dream, he found a very big number $x$. Since he was playing with totient function he immediately applied totient function to $x$ and got a new number $\phi(x)$. But the number was still very large so he again applied totient to it and got another number $\phi(\phi(x))$ which was still way too big. As a result, Euler got frustrated. He wondered how many times he had to apply totient function before reaching $1$. Euler solved it in the dream. Can you do it too?

Formally, let $y_0 = x$

and $y_n = \phi(y_{n-1})$ where $n$ is an integer and $n\ge 1$

Find **smallest** $n$ such that $y_n = 1$

Note: Euler totient function of a positive integer $n$ is defined as the number of positive integers $i$ less than or equal to $n$ such that $gcd(n,i) = 1$

First line of input contains an integer $k ( 1\le k \le 10^5)$

Next line contains $k$ prime numbers $p_1, p_2, … p_k$

Next line contains $k$ integers $e_1,e_2,…e_k$

For each $1\le i\le k$ , $2 \le p_i \le 10^6$

It is guaranteed that each $p_i$ is **pairwise distinct**.

For each $1\le i\le k$ , $1 \le e_i \le 10^6$

Then the input number is calculated as $x =\prod_{i = 1}^{k}p_i^{e_i}$

Print the **smallest** positive $n$ such that $y_n = 1$

Since $n$ can be very large, output it modulo $998244353$

Input | Output |
---|---|

2 3 2 1 1 | 2 |

Input | Output |
---|---|

1 11 1 | 4 |

Login to submit.

77%
Solution Ratio

kawchar85Earliest,

KnightshadeFastest, 0.0s

NiloyDas19Lightest, 7.5 MB

kotoshogiku.510125Shortest, 923B

Toph uses cookies. By continuing you agree to our Cookie Policy.