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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, 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