The Teachers Machine
All submissions for this problem are available.
A new hardware machine is made by the teachers of a smart school.The machine has N buttons with a screen attached to it.The machine works as follows
1. If a button on the machine is pressed odd number of times then it outputs 1 on the screen.
2. If a button on the machine is pressed even number of times then it outputs 0 on the screen.
All the buttons are provided with the position numbers which are in ascending order starting from 1 to N.The button produces the output on the screen according
to their positions (For Ex: if a button at position 2 is pressed once then it will output 1 at the second position).
The teachers wants to check whether the machine is working properly or not.They conduct an experiment in their school.They create a group of S students.The
teacher then sends one student at one time in the room in which the machine is placed.The students had given some instructions by the teachers as follows:
1. The first student entering the room will not press any button on the machine.
2. The next students will then press all the buttons once except the buttons whose position numbers are same as the multiples of the entering position of the student in the room.
After all the students completed the experiment there will be an output on the screen in the form of 0's and 1's. The teacher wants a computer program in order
to verify the output. Your task is find the output that will be present on the screen.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The second line contains two integers N and S. Where N is the number of buttons in the machine and S is the number of students in the group.
- For each test case, output a single line containing the number on the screen.
- 1 ≤ T ≤ 120
- 1 ≤ N ≤ 1000000000
- 1 ≤S ≤ 1000000000
- S ≤ N
2 10 4 7 7Output:
Example case 2:
The number of buttons is 7 and there are 7 students in a group.
First student enters in the room and come out without pressing any buttons.The second student enters the room. He or she presses all the buttons except those which are multiple of his or her entering position.The entering position is 2. The multiples of 2 upto 7(since there are 7 buttons) are 2,4 and 6.
So except the buttons at position 2,4 and 6, the student will press all the buttons once.
Hence the buttons at position 1,3,5 and 7 are pressed once.The buttons which are pressed odd number of times will output 1.This process continues until the student at 7th position
After completing the whole process,the buttons at position 2,3,5,6 and 7 are pressed odd number of times.While the buttons at position 1 and 4 are pressed even number of times.So the output screen will display 0110111.
The first bit is 0 as the button at first position is pressed even number of times,the second bit is 1 as the button at second position is pressed odd number of times and so on.
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.