题目
2024-09-21 16:45:43
发布于:广东
勾股定理
题目描述
沫沫最近在研究勾股定理。对于两个正整数 A 与 B,若存在正整数 C 使得 A2+B2=C2,且 A 与 B 互质,则称(A,B)为一个互质勾股数对。
有一天,沫沫得到了 N 根木棍,其长度都是正整数,她准备从中挑选出若干根木棍来玩拼图游戏,为了使拼出的图案有凌乱美,她希望挑选出的木棍中任意两根的长度均不是互质勾股数对。现在,沫沫想知道有多少种满足要求的挑选木棍的方案。由于答案可能很大,你只要输出答案对 10
9
+7 取模的结果。
提示
样例解释:(5,12)与(12,35)是互质勾股数对,故满足要求的挑选木棍的方案有8种,即:
{5},{12},{35},{5},{5,35},{35,5},{5,5},{5,35,5}。
输入格式
从文件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
这里空空如也
有帮助,赞一个