P3704 [SDOI2017]数字表格

    • 131通过
    • 358提交
  • 题目提供者 ElevenDimensions
  • 评测方式 云端评测
  • 标签 各省省选 2017 山东 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2000ms-3000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Doris刚刚学习了fibonacci数列。用$f[i]$ 表示数列的第$i$ 项,那么

    $f[0]=0$ ,$f[1]=1$ ,

    $f[n]=f[n-1]+f[n-2],n\geq 2$

    Doris用老师的超级计算机生成了一个$n×m$ 的表格,

    第$i$ 行第$j$ 列的格子中的数是$f[\gcd(i,j)]$ ,其中$\gcd(i,j)$ 表示$i,j$ 的最大公约数。

    Doris的表格中共有$n×m$ 个数,她想知道这些数的乘积是多少。

    答案对$10^9+7$ 取模。

    输入输出格式

    输入格式:

    有多组测试数据。

    第一个一个数$T$ ,表示数据组数。

    接下来$T$ 行,每行两个数$n,m$

    输出格式:

    输出$T$ 行,第$i$ 行的数是第$i$ 组数据的结果

    输入输出样例

    输入样例#1: 复制
    3
    2 3
    4 5
    6 7
    输出样例#1: 复制
    1
    6
    960

    说明

    对$10\%$ 的数据,$1\leq n,m\leq 100$

    对$30\%$ 的数据,$1\leq n,m\leq 1000$

    另外存在$30\%$ 的数据,$T\leq 3$

    对$100\%$ 的数据,$T\leq1000,1\leq n,m\leq 10^6$

    时间限制:5s

    内存限制:128MB

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