| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12241 | Restaurants in Hsinchu |
|
| 12301 | Uncle Huang choose Tutor(Easy version) |
|
Description
After some hard work of finding his queen, Knuckles finally arrived NTHU!
Knuckles is exhausted. He wants to grab some delicious food. However, as all of us know......
THERE IS NO "DELICIOUS" FOOD IN HSINCHU.
(Actually there are some restaurants that are not bad. But just "not bad"...)
This truth, which is cruel, hits Knuckles pretty hard. Knuckles doesn't give up and start his journey of finding delicious food in Hsinchu.
However, the more he goes out and seeks, the truth is just getting more clear...
The i-th time that those bad-taste restaurants Knuckles found is Fi . Knuckles found that F1 = 1, F2 = 1, and Fi = Fi-1 + Fi-2 .
The more Knuckles goes out, the more bad-taste restaurants he found.
He is tired of finding more and more bad restaurants. He just wants to know there are how many bad restaurants when he goes out for the i-th time.
- There's a sequence F.
- F1 = 1, F2 = 1, Fi = Fi-1 + Fi-2.
- Find out Fi .
Hint：
Input
The input contains multiple lines, ended by EOF.
Every line contains an integer i.
1 <= i <= 1018.
There will be at most 20 lines.
Output
Output Fi.
Because Fi might be too big, the answer should mod 109+7, which means you should output Fi % (109+7).
Remember to print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Uncle Huang wants to find a tutor. He has n students to choose from.
Students are indexed 1, 2, . . . , n and standing in a circle.
Uncle Huang will count every k-th students in clock-wise.
The k-th student is going to be chosen but the student will disappear(Nobody knows why!) therefore Uncle Huang will continue his counting and start from the next student.
The last remaining student will be his tutor.
Tell Uncle Huang the index of the student who will be his tutor.
example: If n = 5, k = 7
Hint: 約瑟夫斯問題(https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98)
This problem is partial judge.
Note: k might be very large, if you just count k students you will get TLE. Try to count less by using mod.
Input
The input will end by EOF
Every testcase only contains two integer n(1<= n <= 1000) and k(1 <= k <= 109)
Output
For each testcase print the index of the student who last remaining.
remember to print \n at the end of every output.