#HDR001B. 「MCOI-0X」双子

「MCOI-0X」双子

题目背景

你听过三位一体结吗?三个空间用一个循环结连接在一起,不断闭环。

三个空间又指什么呢?循环结的维护者又是谁呢?

出生于主世界的玩家的虚拟体 Steve,应该内心已经有了答案。

题目描述

主世界可以观察地狱和末地,地狱和末地可以转化为两个长为 nn 的序列 ai,bia_i,b_i,称满足下面这个要求:

$$\gcd(a_l,a_{l+1},\cdots,a_r)=\text{lcm}(b_l,b_{l+1},\cdots,b_r) $$

的区间 [l,r][l,r] 为相克区间。

Steve 是你的虚拟体,他问你:

  • 最长的相克区间长度是多少?
  • 一共有多少个相克区间?

答案对 998244353998244353 取模。

输入格式

第一行一个整数 nn 代表序列长度。

第二行 nn 个整数代表序列 aia_i

第三行 nn 个整数代表序列 bib_i

输出格式

一行空格隔开的两个整数:

  • 最长相克区间长度。
  • 相克区间个数。

答案对 998244353998244353 取模。

5
18 10 8 4 12
2 2 2 2 2
5 7

说明/提示

样例 1 解释

满足要求的区间如下:

  • [1,2][1,2],长度为 22
  • [1,3][1,3],长度为 33
  • [2,3][2,3],长度为 22
  • [1,4][1,4],长度为 44
  • [2,4][2,4],长度为 33
  • [1,5][1,5],长度为 55
  • [2,5][2,5],长度为 44

一共有 77 个区间满足要求,最长的区间长度为 55

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(10 pts):n10n \le 10
  • Subtask 2(20 pts):n1000n \le 1000
  • Subtask 3(30 pts):ai,bi10a_i,b_i \le 10
  • Subtask 4(40 pts):无特殊限制。

对于 100%100\% 的数据,1n1051 \le n \le 10^51ai,bi10001 \le a_i,b_i \le 1000