All Tracks Math Number Theory Basic Number Theory-2 Problem

Zoro and Chocolates

Easy-Medium, Number Theory, Segment Trees


Once when Zoro was travelling he saw N box of chocolates in front of him along with the 2 guardians. The King of the Jungle Kaido is very smart and has labeled each box with an ID number(not unique). He has set the number of chocolates in a box in different way.

Let D be the ID number of a box. Then number of chocolates in a box is the sum of all the positive numbers less than equal to D and which have at least 1 common factor with D other than 1. But somehow Zoro gets to know about this trick of Kaido.

Now Zoro has Q chances to get chocolates but the two guardians are protecting the chocolates in a strangely unique way. The left guardian protects all the boxes from the starting box to the box just before his position and the right guardian protects the boxes from the box just after the position where he is standing to the last box. In between the guardians change the boxes with new ID equal to the number of chocolates in the box previously present at that position. (number of chocolates in the new box is according to the kings rule)

Now all the other boxes are unguarded so Zoro has a chance to steal chocolates from them. But unfortunately he can steal chocolates from only one box which is not guarded as it will alert the guardians.

Help Zoro steal one box which has the maximum number of chocolates. Output the number of chocolates in that box.

If the number of chocolates are greater than \( 10^{6}+3 \) then modulo it by \( 10^{6}+3 \)
Please use fast I/O

Input First line contains an integer T denoting the number of test cases.
Each test case is defined as:
Next line contains N and Q denoting the number of boxes and the number of chances.
Next N lines indicates the ID number of all the boxes from 1 to N.
Next Q lines describes the chances. If the chance is 1 L R then it is of the first type which shows the position of the Left guardian and R indicates the position of the Right guardian.
If the chance is 2 Ind then the boxes at index Ind should be replaced by box with ID described above.
Output the number of maximum chocolates that Zoro can get from a unguarded box for the query of type 1.


\(1 \le T \le 10^{3}\)
\(1 \le N \le 2000\)
\(1 \le Q \le 2*10^{3}\)
\(1 \le D \le 10^{6} + 5\)
\(1 \le L \le R \le N\)
\(1 \le ind \le N \)

4 4
3 2 4 5
1 1 3
1 2 2
2 4
1 1 4

The ID of the first BOX is 3 so the number of chocolates in the BOX will be 3 as only 3 has a common factor with itself.
The ID of the BOX 2 is 2 so the number of chocolates is 2 itself as there is no number less than 2 common with 2 other than itself.
Similarly number of chocolates in the 3rd BOX is 6 as 2 and 4 have common factor with 4. So the sum will be 2+4=6.
Similarly number of chocolates in the 4th BOX will be 5.
Now for the first query BOX 1, 2 and 3 are not guarded by the guardians so the maximum chocolates is in BOX 3. So Zoro will be able to get maximum of 6 chocolates.

Time Limit: 3,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: Bash, 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, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

The LNM Institute of Information Technology

Challenge Name

LNMIIT Algorithms Cup - June 2017

View All Notifications