P3307 [SDOI2013]项链

    • 129通过
    • 703提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 数论,数学 最大公约数,gcd 逆元 2013 山东 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 3000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    项链是人体的装饰品之一,是最早出现的首饰。项链除了具有装饰功能之外,有些项 链还具有特殊显示作用,如天主教徒的十字架链和佛教徒的念珠。

    从古至今人们为了美化人体本身,也美 化环境,制造了各种不同风格,不同特点、不同式样的项链,满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论,首饰市场上的项链有黄金、白银、珠宝等几种。

    珍珠项链为珍珠制成的饰品,即将珍珠 钻孔后用线串在一起,佩戴于项间。天然珍珠项链具有一定的护养作用。 最近,铭铭迷恋上了一种项链。与其他珍珠项链基本上相同,不过这种项链的珠子却 与众不同,是正三菱柱的泰山石雕刻而成的。

    三菱柱的侧面是正方形构成的,上面刻有数字。 能够让铭铭满意的项链必须满足下面的条件:

    1:这串项链由n颗珠子构成的。

    2:每一个珠子上面的数字x,必须满足0<x<=a,且珠子上面的数字的最大公约数要恰 好为1。两个珠子被认为是相同的,当且仅当他们经过旋转,或者翻转后能够变成一样的。

    3:相邻的两个珠子必须不同。

    4:两串项链如果能够经过旋转变成一样的,那么这两串项链就是相同的! 铭铭很好奇如果给定n和a,能够找到多少不同串项链。由于答案可能很大,所以对输 出的答案mod 1000000007。

    输入输出格式

    输入格式:

    数据由多组数据构成: 第一行给定一个T<=10,代表由T组数据。 接下来T行,每行两个数n和a。

    输出格式:

    对于每组数据输出有多少不同的串。

    输入输出样例

    输入样例#1: 复制
    1
    2  2
    输出样例#1: 复制
    3

    说明

    对于100%的数据:所有的n<=10^14,a<=10^7,T<=10;

    样例解释:由三种珠子:[1,1,1],[1,1,2],[1,2,2].组成的串有:[1,2],[1,3],[2,3]。

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