Jesse & Heisenberg's Experiment
Practice
2 (5 votes)
Easy Medium
Problem
82% Success 3221 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code
In the lab, Jesse & Heisenberg were experimenting with some formulas that they made for synthesizing their product. To come up with a new product, Heisenberg arranged different molecular weights which are integers in the form of a series. The resulting series goes like -
1,1,2,3,5,8,13....
"Yo, Mr. White! I don't understand any damn thing."
"Just do as I say, Jesse. This is how things work in science."
In order to synthesize a new product, Heisenberg needs to find out HCF (Highest Common Factor) of given two terms from the series modulo 109+7.
He gives this job to Jesse, and asks him to complete this as soon as possible. Jesse has no clue about the series, so he wants your help.
"Yo, Help me out bro!"
INPUT
- First line contains an integer T, the number of Test Cases.
- Next T lines contains two space separated integers M and N in each line
OUTPUT
- Output should contain exactly T lines. Each line containing the answer (HCF of the Mth & Nth term of the series modulo 109+7).
CONSTRAINTS
- 1 ≤ T ≤ 100000
- 1 ≤ M,N ≤ 106
Submissions
Please login to view your submissions
Similar Problems
Points:30
21 votes
Tags:
SortingIntegerModulus ArithmeticModulesC++Number TheoryMathematics
Points:30
3 votes
Tags:
MathematicsModular arithmeticEasy-Medium
Points:30
13 votes
Tags:
MathematicsModular arithmeticEasy-Medium
Editorial