P3172 [CQOI2015]选数

    • 149通过
    • 449提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 最大公约数,gcd 莫比乌斯反演 递推 2015 重庆 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    我们知道,从区间[L,H](L和H为整数)中选取N个整数,总共有(H-L+1)^N种方案。小z很好奇这样选出的数的最大公约数的规律,他决定对每种方案选出的N个整数都求一次最大公约数,以便进一步研究。然而他很快发现工作量太大了,于是向你寻求帮助。你的任务很简单,小z会告诉你一个整数K,你需要回答他最大公约数刚好为K的选取方案有多少个。由于方案数较大,你只需要输出其除以1000000007的余数即可。

    输入输出格式

    输入格式:

    输入一行,包含4个空格分开的正整数,依次为N,K,L和H。

    输出格式:

    输出一个整数,为所求方案数。

    输入输出样例

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

    说明

    样例解释

    所有可能的选择方案:(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)

    其中最大公约数等于2的只有3组:(2, 2), (2, 4), (4, 2)

    对于100%的数据,1<=N,K<=10^9,1<=L<=H<=10^9,H-L<=10^5

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