P3213 [HNOI2011]勾股定理

    • 20通过
    • 62提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 最大公约数,gcd 枚举,暴力 连通块 2011 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    沫沫最近在研究勾股定理。对于两个正整数 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

    说明

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

    {5},{12},{35},{5},{5,35},{35,5},{5,5},{5,35,5}。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。