#P3213. [HNOI2011] 勾股定理

    ID: 4050 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2011湖南枚举连通块最大公约数 gcd

[HNOI2011] 勾股定理

题目描述

沫沫最近在研究勾股定理。对于两个正整数 AABB,若存在正整数 CC 使得 A2+B2=C2A^2+B^2=C^2,且 AABB 互质,则称 (A,B)(A,B) 为一个互质勾股数对。

有一天,沫沫得到了 NN 根木棍,其长度都是正整数,她准备从中挑选出若干根木棍来玩拼图游戏,为了使拼出的图案有凌乱美,她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在,沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大,你只要输出答案对 109+710^9+7 取模的结果。

输入格式

第一行是一个正整数 NN,表示共有多少根木棍。

第二行是用空格隔开的 NN 个正整数 h1,h2,,hNh_1, h_2, \cdots, h_N,其中对 1iN1≤i≤Nhih_i 表示第 ii 根木棍的长度。

输入的数据保证 30%30\% 的数据满足对 1iN1≤i≤N1hi30001≤h_i≤3000

另外 30%30\% 的数据满足对 1iN1≤i≤N1hi2×1051≤h_i≤2\times10^5

剩下的 40%40\% 的数据满足对 1iN1≤i≤N2×104hi1062\times10^4≤h_i≤10^6

100%100\% 的数据满足 N106N≤10^6

输出格式

输出仅包含一个非负整数,表示满足要求的挑选木棍的方案数对 109+710^9+7 取模的结果。

4				
5 12 35 5	

8

提示

样例解释:(5,12)(5,12)(12,35)(12,35) 是互质勾股数对,故满足要求的挑选木棍的方案有 88 种,即:

$\{5\},\{12\},\{35\},\{5\},\{5,35\},\{35,5\},\{5,5\},\{5,35,5\}$。