P3362 Cool loves shaxian

    • 29通过
    • 433提交
  • 题目提供者 Scarlet
  • 评测方式 云端评测
  • 标签 数论,数学 洛谷原创 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    Cool 非常非常喜欢吃沙县,确切地说,他非常非常把各种无辜群众拉到沙县去吃饭(╯‵□′)╯(┻━┻。大家都非常非常想知道沙县到底给了 Cool 多少钱带盐沙县小吃,以便未来威逼利诱 Cool 来请客吃隔壁的 KFC。经过多方追踪,大家发现了带盐费发放的某一些规律ヾ(o◕∀◕)ノヾ。

    题目描述

    沙县发放带盐费以壕著称。这家沙县发放带盐费时有个指数d。他会发放n轮带盐费,在第i轮中,都会发放f(i) = ∑ k|i k d (i ≤ n)这么多的钱。

    现在大家有了Q个问题,每个问题都形如 Cool 参加从第L i 轮到第R i 轮的带盐活动,将能获得多少钱。(保证1 ≤ L i ≤ R i ≤ n (1 ≤ i ≤ Q))

    由于开在南大街的沙县小吃不是一般的有钱啊,所以呢,我们要计算的是

    Cool 收到的钱对10^ 9 + 7取模得到的答案。

    输入输出格式

    输入格式:

    输入包含若干行。

    第一行,三个整数,n, d, Q

    接下来的Q行,每行两个整数L i , R i

    输出格式:

    输出包含Q行

    每行一个整数,表示 Cool 得到的带盐费。

    输入输出样例

    输入样例#1: 复制
    10 2 2
    4 5
    8 10
    输出样例#1: 复制
    47
    306
    输入样例#2: 复制
    1000 0 1
    720 720
    输出样例#2: 复制
    30

    说明

    样例1:

    f(4) = 1^2 + 2^2 + 4^2 = 21

    f(5) =1^2+5^2= 26

    f(8) + f(9) + f (10) = 85 + 91 + 130= 306

    样例2:

    就相当于在数720的因数个数呢~

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