← 返回题目
题库练习 勾股定理
← 上一题 下一题 →

A2279 | 勾股定理

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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


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

输入格式

从文件input.txt中读入数据，输入文件第一行是一个正整数N，表示共有多少根木棍。

输入文件第二行是用空格隔开的N个正整数h1, h2, …, hN，其中对1≤i≤N，hi表示第i根木棍的长度。

输入的数据保证30%的数据满足对$1≤i≤N$有$1≤h_i≤3000$，

另外30%的数据满足对$1≤i≤N$有$1≤hi≤200000$，

剩下的40%的数据满足对$1≤i≤N$有$20000≤h_i≤1000000$，

100%的数据满足$N≤1000000$。

输出格式

输出文件 output.txt 仅包含一个非负整数，表示满足要求的挑选木棍的方案数对 109+7 取模的结果。

输入输出样例

输入 #1
4				
5 12 35 5
输出 #1
8
C++ 编辑器
输入
输出