#P16061. [Oni2021国家队选拔赛]Pastile

    ID: 15272 传统题 250ms 128MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高双射计数莫比乌斯反演线性筛一维前缀和快速幂

[Oni2021国家队选拔赛]Pastile

题目描述

Robert 厌倦了自己的白色 T 恤,于是决定把它染成自己最喜欢的颜色:蓝色。

他的朋友 Georgian 给了他若干片蓝色染色药片,共有 NN 种不同的蓝色初始色调。对于第 ii 种色调,Robert 有 pip_i 片药片。

为了染色,Robert 会把 T 恤和若干药片一起放入洗衣机中。他想制造一种新的蓝色色调,于是选择整数

a1,a2,…,aNa_1,a_2,\ldots,a_N

其中 aia_i 表示使用第 ii 种初始色调的药片数量。要求:

1≤ai≤pi1\le a_i\le p_i

也就是说,每种初始色调至少使用一片,且不能超过已有数量。

两个选择方案

a1,a2,…,aNa_1,a_2,\ldots,a_N

和

b1,b2,…,bNb_1,b_2,\ldots,b_N

会被认为染出了同一种新色调,当且仅当:

$$\frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots=\frac{a_N}{b_N}.$$

请计算 Robert 最多可以制造出多少种不同的新蓝色色调。由于答案可能很大,只需要输出答案对

1 000 000 0071\,000\,000\,007

取模后的结果。

输入格式

第一行包含一个整数 NN,表示初始色调的数量。

第二行包含 NN 个整数:

p1,p2,…,pNp_1,p_2,\ldots,p_N

其中 pip_i 表示第 ii 种初始色调已有的药片数量。

输出格式

输出一行一个整数,表示可以形成的不同新色调数量,对 1 000 000 0071\,000\,000\,007 取模。

数据范围与约定

记:

$$V_{\min}=\min(p_1,p_2,\ldots,p_N),\qquad V_{\max}=\max(p_1,p_2,\ldots,p_N).$$

保证:

  • 1≤N≤2000001\le N\le 200000;
  • 1≤Vmin⁡≤Vmax⁡≤2000001\le V_{\min}\le V_{\max}\le 200000。

子任务

子任务 分值 限制
1 2 Vmin⁡=1V_{\min}=1
2 6 1≤N,Vmax⁡≤71\le N,V_{\max}\le 7
3 4 1≤N,Vmax⁡≤81\le N,V_{\max}\le 8
4 16 1≤N,Vmax⁡≤1001\le N,V_{\max}\le 100
5 11 1≤N,Vmax⁡≤10001\le N,V_{\max}\le 1000
6 7 1≤N,Vmax⁡≤50001\le N,V_{\max}\le 5000
7 15 1≤N,Vmax⁡≤300001\le N,V_{\max}\le 30000
8 10 Vmin⁡=Vmax⁡V_{\min}=V_{\max}
9 8 1≤Vmin⁡≤1001\le V_{\min}\le 100
10 21 无额外限制

样例

样例 1

3
2 3 2
11

样例 2

4
7 7 7 7
2303

样例 3

7
15 8 19 7 15 8 19
36191027

样例 4

2
31124 150719
851838928

样例解释

对于第一个样例,共有 1111 种可能的新色调:

  • ⟨1,1,1⟩\langle 1,1,1\rangle,它与 ⟨2,2,2⟩\langle 2,2,2\rangle 相同;
  • ⟨1,1,2⟩\langle 1,1,2\rangle;
  • ⟨1,2,1⟩\langle 1,2,1\rangle;
  • ⟨1,2,2⟩\langle 1,2,2\rangle;
  • ⟨1,3,1⟩\langle 1,3,1\rangle;
  • ⟨1,3,2⟩\langle 1,3,2\rangle;
  • ⟨2,1,1⟩\langle 2,1,1\rangle;
  • ⟨2,1,2⟩\langle 2,1,2\rangle;
  • ⟨2,2,1⟩\langle 2,2,1\rangle;
  • ⟨2,3,1⟩\langle 2,3,1\rangle;
  • ⟨2,3,2⟩\langle 2,3,2\rangle。