D. My pretty girl Noora

Codeforces

IDCF822D

Time1000ms

Memory256MB

Difficulty—

brute forcedpgreedymathnumber theory

English · Original

Chinese · Translation

Formal · Original

In Pavlopolis University where Noora studies it was decided to hold beauty contest "Miss Pavlopolis University". Let's describe the process of choosing the most beautiful girl in the university in more detail. The contest is held in several stages. Suppose that exactly _n_ girls participate in the competition initially. All the participants are divided into equal groups, _x_ participants in each group. Furthermore the number _x_ is chosen arbitrarily, i. e. on every stage number _x_ can be different. Within each group the jury of the contest compares beauty of the girls in the format "each with each". In this way, if group consists of _x_ girls, then comparisons occur. Then, from each group, the most beautiful participant is selected. Selected girls enter the next stage of the competition. Thus if _n_ girls were divided into groups, _x_ participants in each group, then exactly participants will enter the next stage. The contest continues until there is exactly one girl left who will be "Miss Pavlopolis University" But for the jury this contest is a very tedious task. They would like to divide the girls into groups in each stage so that the total number of pairwise comparisons of the girls is as few as possible. Let _f_(_n_) be the minimal total number of comparisons that should be made to select the most beautiful participant, if we admit _n_ girls to the first stage. The organizers of the competition are insane. They give Noora three integers _t_, _l_ and _r_ and ask the poor girl to calculate the value of the following expression: _t_0·_f_(_l_) + _t_1·_f_(_l_ + 1) + ... + _t__r_ - _l_·_f_(_r_). However, since the value of this expression can be quite large the organizers ask her to calculate it modulo 109 + 7. If Noora can calculate the value of this expression the organizers promise her to help during the beauty contest. But the poor girl is not strong in mathematics, so she turned for help to Leha and he turned to you. ## Input The first and single line contains three integers _t_, _l_ and _r_ (1 ≤ _t_ < 109 + 7, 2 ≤ _l_ ≤ _r_ ≤ 5·106). ## Output In the first line print single integer — the value of the expression modulo 109 + 7. [samples] ## Note Consider the sample. It is necessary to find the value of . _f_(2) = 1. From two girls you can form only one group of two people, in which there will be one comparison. _f_(3) = 3. From three girls you can form only one group of three people, in which there will be three comparisons. _f_(4) = 3. From four girls you can form two groups of two girls each. Then at the first stage there will be two comparisons, one in each of the two groups. In the second stage there will be two girls and there will be one comparison between them. Total 2 + 1 = 3 comparisons. You can also leave all girls in same group in the first stage. Then comparisons will occur. Obviously, it's better to split girls into groups in the first way. Then the value of the expression is .

在诺拉就读的帕夫洛波利斯大学，决定举办一场名为"帕夫洛波利斯大学小姐"的选美比赛。让我们更详细地描述一下如何在大学中选出最美丽的女孩。比赛分为若干轮进行。假设最初有 #cf_span[n] 名女生参加比赛。所有参赛者被划分为若干组，每组 #cf_span[x] 人。其中，数字 #cf_span[x] 可以任意选择，即每一轮的 #cf_span[x] 都可以不同。在每组内部，评委以"每两人互比"的方式比较女生的美貌，因此，如果一组有 #cf_span[x] 名女生，则会发生 #cf_span[\binom{x}{2}] 次比较。然后，从每组中选出最美丽的选手进入下一轮。因此，如果 #cf_span[n] 名女生被分为每组 #cf_span[x] 人的若干组，则恰好有 #cf_span[\frac{n}{x}] 名选手进入下一轮。比赛持续进行，直到只剩下一名女生，她将成为"帕夫洛波利斯大学小姐"。但对于评委而言，这项比赛非常繁琐。他们希望在每一轮中将女生分组，使得总的两两比较次数尽可能少。设 #cf_span[f(n)] 表示当第一轮有 #cf_span[n] 名女生时，选出最美丽选手所需的最少总比较次数。比赛的组织者非常疯狂。他们给了诺拉三个整数 #cf_span[t]、#cf_span[l] 和 #cf_span[r]，并要求这个可怜的女孩计算以下表达式的值：#cf_span[t_0 \cdot f(l) + t_1 \cdot f(l+1) + \dots + t_{r-l} \cdot f(r)]。然而，由于该表达式的值可能很大，组织者要求她计算其对 #cf_span[10^9 + 7] 取模的结果。如果诺拉能算出这个值，组织者答应在选美比赛中帮助她。但这个可怜的女孩数学不好，于是她向列哈求助，而列哈又找到了你。输入的第一行包含三个整数 #cf_span[t]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 \leq t < 10^9 + 7,\ 2 \leq l \leq r \leq 5 \cdot 10^6]）。在第一行输出一个整数——表达式对 #cf_span[10^9 + 7] 取模的值。考虑样例。需要计算表达式 #cf_span[t_0 \cdot f(2) + t_1 \cdot f(3) + t_2 \cdot f(4)] 的值。 #cf_span[f(2) = 1]。从两名女生中只能组成一组两人，其中发生一次比较。 #cf_span[f(3) = 3]。从三名女生中只能组成一组三人，其中发生三次比较。 #cf_span[f(4) = 3]。从四名女生中可以分成两组，每组两人。第一轮中，每组发生一次比较，共两次；第二轮剩下两名女生，再进行一次比较。总计 #cf_span[2 + 1 = 3] 次比较。你也可以在第一轮让所有女生留在同一组，此时会发生 #cf_span[\binom{4}{2} = 6] 次比较。显然，第一种分组方式更好。因此，表达式的值为 #cf_span[t_0 \cdot 1 + t_1 \cdot 3 + t_2 \cdot 3]。 ## Input 第一行包含三个整数 #cf_span[t]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 \leq t < 10^9 + 7,\ 2 \leq l \leq r \leq 5 \cdot 10^6]）。 ## Output 在第一行输出一个整数——表达式对 #cf_span[10^9 + 7] 取模的值。 [samples] ## Note 考虑样例。需要计算表达式 #cf_span[t_0 \cdot f(2) + t_1 \cdot f(3) + t_2 \cdot f(4)] 的值。 #cf_span[f(2) = 1]。从两名女生中只能组成一组两人，其中发生一次比较。 #cf_span[f(3) = 3]。从三名女生中只能组成一组三人，其中发生三次比较。 #cf_span[f(4) = 3]。从四名女生中可以分成两组，每组两人。第一轮中，每组发生一次比较，共两次；第二轮剩下两名女生，再进行一次比较。总计 #cf_span[2 + 1 = 3] 次比较。你也可以在第一轮让所有女生留在同一组，此时会发生 #cf_span[\binom{4}{2} = 6] 次比较。显然，第一种分组方式更好。因此，表达式的值为 #cf_span[t_0 \cdot 1 + t_1 \cdot 3 + t_2 \cdot 3]。

**Definitions** Let $ f(n) $ denote the minimal total number of pairwise comparisons required to reduce $ n $ girls to one winner, where in each stage, participants are partitioned into groups of size $ x \geq 2 $, and within each group of size $ x $, $ \binom{x}{2} $ comparisons occur; the winner of each group advances to the next stage. **Constraints** 1. $ 1 \leq t < 10^9 + 7 $ 2. $ 2 \leq l \leq r \leq 5 \cdot 10^6 $ **Objective** Compute: $$ \sum_{i=l}^{r} t^{i-l} \cdot f(i) \mod (10^9 + 7) $$

Samples

Input #1

2 2 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "D. My pretty girl Noora",
    "description": {
      "content": "In Pavlopolis University where Noora studies it was decided to hold beauty contest \"Miss Pavlopolis University\". Let's describe the process of choosing the most beautiful girl in the university in mor",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF822D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In Pavlopolis University where Noora studies it was decided to hold beauty contest \"Miss Pavlopolis University\". Let's describe the process of choosing the most beautiful girl in the university in mor...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在诺拉就读的帕夫洛波利斯大学，决定举办一场名为\"帕夫洛波利斯大学小姐\"的选美比赛。让我们更详细地描述一下如何在大学中选出最美丽的女孩。\n\n比赛分为若干轮进行。假设最初有 #cf_span[n] 名女生参加比赛。所有参赛者被划分为若干组，每组 #cf_span[x] 人。其中，数字 #cf_span[x] 可以任意选择，即每一轮的 #cf_span[x] 都可以不同。在每组内部，评委以\"每两人互比\"...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f(n) $ denote the minimal total number of pairwise comparisons required to reduce $ n $ girls to one winner, where in each stage, participants are partitioned into groups of si...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments