D. Хүсэлт

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өнөөдөр математикийн хичээл дээр багш нь Вовочка-д эерэг бүхэл тооны Эйлерийн функц $φ(n)$ гэдэг нь $n$-ээс бага болон тэнцүү $n$-тэй харилцан анхны тоонуудыг тоолдог арифметик функц болохыг хэлж өгчээ.$1$ гэсэн тооны хувьд $φ(1) = 1$ гэж үзнэ.

Одоо багш нь Вовочка-д $n$ ширхэг бүхэл тоо болох $a_{1}, a_{2}, ..., a_{n}$-уудын цувааг өгсөн ба түүнийг $q$ ширхэг $l_{i}$ $r_{i}$ гэсэн хэлбэрээр өгөгдөх асуулт бүрийн хувьд -г $10^{9} + 7$ модулаар бодож олохыг даалгажээ.Энэ даалгавар нь 2-р ангийн сурагчийн хувьд хэтэрхий хүнд учраас Вовочка таны тусламжийг хүсжээ.

Оролт

Эхний мөрөнд Вовочка-д өгөгдөх цувааны уртыг илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 200 000$) өгөгдөнө.2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{6}$)-ууд өгөгдөнө.

3-дахь мөрөнд асуултын тоог илэрхийлэх бүхэл тоо $q$ ($1 ≤ q ≤ 200 000$) өгөгдөнө.Дараагийн $q$ ширхэг мөрийн мөр болгонд нэг асуулт өгөгдөнө.Асуулт бүр нь сегментийн хилүүд болох $l_{i}$ болон $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$)-аар өгөгдөнө.

Гаралт

Асуулт болгоны хувьд Эйлерийн функцийн утгыг $10^{9} + 7$ модулаар бодсон $q$ ширхэг хариуг хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
10
1 2 3 4 5 6 7 8 9 10
7
1 1
3 8
5 6
4 8
8 10
7 9
7 10
Гаралт
1
4608
8
1536
192
144
1152
Оролт
7
24 63 13 52 6 10 1
6
3 5
4 7
1 7
2 4
3 6
2 6
Гаралт
1248
768
12939264
11232
9984
539136

Тэмдэглэл

2-дахь жишээний утгуудыг доорх байдлаар бодно:

  • $φ(13*52*6) = φ(4056) = 1248$
  • $φ(52*6*10*1) = φ(3120) = 768$
  • $φ(24*63*13*52*6*10*1) = φ(61326720) = 12939264$
  • $φ(63*13*52) = φ(42588) = 11232$
  • $φ(13*52*6*10) = φ(40560) = 9984$
  • $φ(63*13*52*6*10) = φ(2555280) = 539136$
Сэтгэгдлүүдийг ачааллаж байна...