P3704 [SDOI2017]数字表格

    • 95通过
    • 265提交
  • 题目提供者ElevenDimensions
  • 标签 各省省选 2017 山东 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2s-3s / 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类违反进行处理。