| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1418
Z同学的乌克兰之旅
Time Limit: 1000ms
Memory Limit: 65536kb Description
Z同学前段时间去了美女如云的乌克兰。夜幕降临，Z同学在看了一天美女后开始解决自己的住宿问题,他打算玩一个小游戏来选择去住宾馆还是去找当地人借宿。面前有M张当地人的联系方式，前M-1个都是东欧大汉，最后一个是乌克兰妹子！开始所有的联系卡片都朝下，总共操作M轮，第i轮时从第一张开始数，每数i张就将该张翻面（正反颠倒），例如第3轮就将第3、6、9……张翻面。结束时若最后一张面朝上，就去勇敢的找当地妹子借宿，反之去住宾馆。  借宿时城市里有N户人家排成一列，编号从1到N。可以任意选择若干家去敲门询问能否留宿，但是Z同学决定不选择相邻的两家，因为他觉着相邻的两家不可能都是美女，也许是隔壁老王？但是每家门都不敲也不好，毕竟晚上不能睡大街。 所以，请问Z同学是去住宾馆或者是总共有多少种选择方式可以询问借宿。 Input
有多组数据，每组输入M (1 ≤ M ≤ 1000000000), N (1 ≤ N ≤ 100000)，二者以空格隔开，含义见题目描述。M,N均为-1时表示输入结束，你不用处理这个数据。 Output
每组输出一行。若住宾馆，则输出"No girl"（无双引号）。反之输出选择方式的总数，因为结果可能很大，所以请输出对10000007取模后的结果。
Sample Input
1 2 2 4 -1 -1 Sample Output
2 No girl Hint
本题FB奖: 白书一本.
Source
zqy
|