시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 123 1 1 100.000%

문제

상근이는 정수를 0부터 m-1까지의 정수로 매핑시키는 해싱 함수 h(y) = a·y + b mod m를 만들었다. x, n, c, d가 주어졌을 때, 해시값 h(x), h(x+1), ..., h(x+n) 중 몇 개가 구간 [c,d]에 포함되는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 105)가 주어진다. 다음 t개 줄에는 a, b, x, n, c, d, m이 주어진다. (1 ≤ m ≤ 1015, c ≤ d < m, a,b < m, x+n ≤ 1015, a·(x+n)+b ≤ 1015) 입력으로 주어지는 모든 수는 음이 아닌 정수이다.

출력

각 테스트 케이스마다 c ≤ a·(x+i)+b mod m ≤ d 을 만족하는 0 ≤ i ≤ n의 개수를 출력한다.

예제 입력 1

2
2 3 1 3 0 1 7
1 0 0 8 0 8 9

예제 출력 1

1
9
W3sicHJvYmxlbV9pZCI6Ijc2MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NzRcdWMyZjEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgMFx1YmQ4MFx1ZDEzMCBtLTFcdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjllNFx1ZDU1MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWQ1NzRcdWMyZjEgXHVkNTY4XHVjMjE4IGgoeSkgPSBhJm1pZGRvdDt5ICsgYiBtb2QgbVx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIHgsIG4sIGMsIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTc0XHVjMmRjXHVhYzEyIGgoeCksIGgoeCsxKSwgLi4uLCBoKHgrbikgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWFjMDAgXHVhZDZjXHVhYzA0IFtjLGRdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMSAmbGU7IHQgJmxlOyAxMDxzdXA+NTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIHRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGEsIGIsIHgsIG4sIGMsIGQsIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG0gJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCBjICZsZTsgZCAmbHQ7IG0sIGEsYiAmbHQ7IG0sIHgrbiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4sIGEmbWlkZG90Oyh4K24pK2IgJmxlOyAxMDxzdXA+MTU8XC9zdXA+KSBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyMThcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgYyAmbGU7IGEmbWlkZG90Oyh4K2kpK2IgbW9kIG0gJmxlOyBkIFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgMCAmbGU7IGkgJmxlOyBuXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzYxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikhhc2hpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIHRoZSBoYXNoIGZ1bmN0aW9uIGgoeSkgPSBhJm1pZGRvdDt5K2IgbW9kIG0gd2hpY2ggbWFwcyBlYWNoIGludGVnZXIgdG8gc29tZSBpbnRlZ2VyIGJldHdlZW4gMCBhbmQgbSZtaW51czsxLiBZb3UgYXJlIGdpdmVuIHgsIG4sIGMsIGQgYW5kIGFyZSBjdXJpb3VzIGhvdyBtYW55IG9mIHRoZSBoYXNoIHZhbHVlcyBoKHgpLCBoKHgrMSksIC4uLiwgaCh4K24pIGxhbmQgaW4gdGhlIGludGVydmFsIFtjLCBkXS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBhIHBvc2l0aXZlIGludGVnZXIgdCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzICgxICZsZTsgdCAmbGU7IDEwPHN1cD41PFwvc3VwPikuIHQgbGluZXMgdGhlbiBmb2xsb3csIHdoZXJlIHRoZSBpdGggbGluZSBnaXZlcyB0aGUgdmFsdWVzIGEsIGIsIHgsIG4sIGMsIGQsIG0sIHNwYWNlLXNlcGFyYXRlZCwgZm9yIHRoZSBpPHN1cD50aDxcL3N1cD4gdGVzdCBjYXNlLiBBbGwgZ2l2ZW4gdmFsdWVzIGFyZSBub24tbmVnYXRpdmUuIEFsc28sIDEgJmxlOyBtICZsZTsgMTA8c3VwPjE1PFwvc3VwPiwgYyAmbGU7IGQgJmx0OyBtLCBhLGIgJmx0OyBtLCB4K24gJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCBhbmQgYSZtaWRkb3Q7KHgrbikrYiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIG9yZGVyIG91dHB1dCB0aGUgbnVtYmVyIG9mIGksIDAgJmxlOyBpICZsZTsgbiwgc3VjaCB0aGF0IGMgJmxlOyBhJm1pZGRvdDsoeCtpKStiIG1vZCBtICZsZTsgZCBpbiB0aGF0IHRlc3QgY2FzZSwgZm9sbG93ZWQgYnkgYSBuZXdsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Individual Round 2008 3번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: kcm1700