P3704 [SDOI2017]数字表格

    • 314通过
    • 831提交
  • 题目提供者 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类违反进行处理。