Make It One

Problem

Chef is given a positive integer $N$ and we have to convert it to $1$ using some operations.$\newline$

In one operation, Chef can do the following:$\newline$

• Choose a prime number $p$ such that $p$ $|$ $N$ $(p$ divides $N)$.
• Replace $N$ with $\frac{N}{p}$.

However, Chef is also given some triggers of the form $(a,b)$ ($a$ is prime). Thus, if we divide by $p$ in some operation, we also have to multiply by $x$ for all triggers of the form $(p,x)$.

For example: Consider $N=18$, and the triggers $(3,4)$ and $(3,2)$ exist. In one operation, if we choose to divide by $3$, we have to multiply the result with $4$ and $2$. In other words, $(18 \mapsto \frac{18}{3} \cdot 4 \cdot 2)=48$. Thus, $18$ is converted to $48$.

Given a number $N$ and $M$ triggers of the form $(a,b)$ (where $a$ is always prime), find the minimum number of operations required to convert $N$ to $1$ modulo $998244353$. Print $-1$ if it is not possible to do so.

Input Format

• The first line of each input contains two integers $N$ and $M$ - the initial integer and the number of triggers given to the Chef.
• The next $M$ lines describe the triggers. The $i^{th}$ of these $M$ lines contains two space-separated integers $a$ and $b$, denoting that Chef has to multiply by $b$ if he choses to divide by $a$ in some operation.
• It is guaranteed that $(a_i, b_i) \ne (a_j, b_j)$ for $i \ne j$.

Output Format

Output on a new line, the minimum number of operations required to convert $N$ to $1$, or print $-1$ if it is not possible to do so. In case it is possible to convert $N$ to $1$, the minimum number of operations can be large, so output it modulo $998244353$.

Constraints

• $1 \leq N \leq 10^6$
• $0 \leq M \leq 10^5$
• $1 \leq a \leq 10^6$
• $1 \leq b \leq 10^6$
• $a$ is a prime number.

Sample 1:

Input

Output

6 1
2 3

3

Explanation:

We can convert $6$ to $1$ using $3$ operations in the following way:

• Divide $6$ by $3$. Since no trigger of the form $(3,x)$ exists, $6$ converts to $\frac{6}{3}= 2$.
• Divide $2$ by $2$. Since $(2,3)$ exists, $2$ is converted to $2 \mapsto \frac{2}{2} \cdot 3 = 3$. - Divide $3$ by $3$. Since no trigger of the form $(3,x)$ exists, $3$ converts to $\frac{3}{3}= 1$.

It can be proven that we cannot convert $6$ to $1$ in less than $3$ operations.

Sample 2:

Input

Output

4 3
2 5
2 3
3 7

8

Sample 3:

Input

Output

2 3
2 3
3 5
5 3

-1

Explanation:

We can not convert $2$ to $1$

$1$ using any finite number of operations. 

#include "bits/stdc++.h"

// #pragma GCC optimize("O3,unroll-loops")

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

using ll = long long int;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()

{

ios::sync_with_stdio(false); cin.tie(0);

const int LIM = 1e6 + 5, mod = 998244353;

vector<int> spf(LIM);

for (int i = LIM-1; i >= 2; --i) {

for (int j = i; j < LIM; j += i) spf[j] = i;

}

int n, m; cin >> n >> m;

vector<vector<int>> adj(LIM);

for (int i = 0; i < m; ++i) {

int a, b; cin >> a >> b;

while (b > 1) {

int p = spf[b];

b /= p;

adj[a].push_back(p);

}

}

int ans = 0, bad = 0;

vector<int> cost(LIM, -1), mark(LIM);

auto calc = [&] (const auto &self, int u) -> ll {

if (cost[u] != -1) return cost[u];

if (mark[u] == 1 or bad) {

bad = 1;

return 0;

}

mark[u] = 1;

ll ret = 1;

for (int v : adj[u]) {

ret += self(self, v);

ret %= mod;

}

mark[u] = 2;

return cost[u] = ret;

};

while (n > 1) {

int p = spf[n];

ans += calc(calc, p); ans %= mod;

n /= p;

}

if (bad) cout << -1 << '\n';

else cout << ans << '\n';

}