All Tracks Math Number Theory Problem

Vasya and Mathematical Analysis
Tag(s):

Easy-Medium, Math, Number Theory, Sieve

Problem
Editorial
Analytics

It's an extremely cold day in BitLand and Vasya is in the mood to do some complex arithmetic. So, he defines the following 2 functions:

\(F(x)\) : Largest divisor of number x that is \(< x\).

\(Q(A,l,r)\): Product of \(F(x)\) where \(l \le x \le r\) in a certain array A

Now, Vasya has been given an array A of size N. He needs to answer certain types of queries based on this array. In each query. he shall be given 2 integers l and r and he needs to find \(Q(A,l,r)\) He find this task too easy and has passed it on to you. Can you do it. As the answer to each query can be relatively large, find it Modulo \(10^9+7\)

Input Format :

The first line contains a single integers N denoting the size of array A. The next line contains N space separated integers denoting the elements of array A. The next line contains a single integer T denoting the number of queries. Each of the next T lines contain 2 integers l and r.

Output Format:

Print the answer to each query on a new line. As the answer may be large, print it Modulo \(10^9+7\)

Constraints:

\( 1 \le N \le 10^6 \)

\( 2 \le A[i] \le 10^7 \)

\( 1 \le T \le 10^5 \)

\( 1 \le l \le r \le N \)

SAMPLE INPUT
4
4 9 9 2
2
1 3
2 4
SAMPLE OUTPUT
18
9
Explanation

For query 1, \(F(4)\)= 2, \(F(9)\) = 3. So, the answer to the query = \(2\times 3 \times3\) = \( 18\%(10^9+7)\) = \(18\)

For query 2, \(F(9)\) = 3 , \(F(2)\)= 1. So, the answer to the query = \(3\times 3 \times1\) = \(9\%(10^9+7)\) = 9

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Sapient Global Markets

Challenge Name

Sapient Global Markets Core Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?