#PQJ1489x8000. QOJ 1489_8000

    ID: 2617 传统题 1500ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SNOI 2024线段树

QOJ 1489_8000

2024 年陕西省NOI 省队选拔赛试题 第二试平方数(square) 平方数(square) 【题目描述】 你有一个正整数序列a1, a2, . . . , an。请问有多少个区间的乘积是完全平方数。也就 是有多少对(l, r)(1 ≤l ≤r ≤n),满足!r i=l ai 是完全平方数。 【输入格式】 从文件square.in 中读入数据。 第一行一个整数n 表示数字个数。 接下来一行,每行n 个数,表示a1, a2, . . . , an。 【输出格式】 输出到文件square.out 中。 输出一个整数,表示有多少对区间的乘积是完全平方数。 接下来按照字典序输出这些区间,也就是按照l 从小到大输出。 如果有多个l 相同的区间,按照r 从小到大输出。如果区间个数超过105 个,输出 前105 个即可。 【样例1 输入】 1 10 2 1 2 3 4 6 8 9 12 16 18 【样例1 输出】 1 12 2 1 1 3 1 5 4 2 5 5 3 6 6 3 7 7 4 4 8 4 8 9 4 9 10 5 8 11 5 9 12 7 7 第2 页 共9 页

2024 年陕西省NOI 省队选拔赛试题 第二试平方数(square) 13 9 9 【样例2 输入】 1 3 2 999999999999999956000000000000000363 3 999999999999999844000000000000004059 4 999999999999999866000000000000001353 【样例2 输出】 1 1 2 1 3 【样例解释】 在第二个样例中,这三个数为1018 −11, 1018 −33, 1018 −123 两两相乘。 【样例3】 见下发文件中square/square3.in 与square/square3.ans。 这个样例满足测试点4 ∼6 的条件限制。 【样例4】 见下发文件中square/square4.in 与square/square4.ans。 这个样例满足测试点11 ∼14 的条件限制。 【样例5】 见下发文件中square/square5.in 与square/square5.ans。 这个样例满足测试点18 ∼20 的条件限制。 【数据范围】 对于所有的数据,保证1 ≤n ≤3 × 105, 1 ≤ai ≤1036。 具体如下: 第3 页 共9 页

2024 年陕西省NOI 省队选拔赛试题 第二试平方数(square) 测试点编号 n ≤ ai ≤ 1 ∼3 1000 104 4 ∼6 105 106 7 ∼10 100 1036 11 ∼14 1000 15 ∼17 105 18 ∼20 3 × 105 第4 页 共9 页