请教hacker cup 之auction的算法

btdm123

这是原题：

Auction

    Download input file
    Submit answers
    Time Expired

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.

One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.

If product i has price Pi and weight Wi, then the following holds for product i+1:

    Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
    Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)

You carefully calculated the parameters for the generator (P1, W1, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.
Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P1, W1, M, K, A, B, C and D.
Output

Output T lines, one for each test case. For each case, output "Case #t: a b", where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.
Constraints

    1 ≤ T ≤ 20
    1 ≤ N ≤ 1018
    1 ≤ M, K ≤ 107
    1 ≤ P1 ≤ M
    1 ≤ W_1 ≤ K
    0 ≤ A,B,C,D ≤ 109

Example inputExample output

5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19

Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1


我写的程序算example的数据没有问题，但真正的input file却是：

20
34468440 999999 12347 9699690 9748872 378288879 843875938 672672191 643425609
81834165 9999991 1 9999991 9999989 389999650 169999844 799999121 149999837
918495108443110920 9999991 1 9999991 9999989 849999236 589999466 309999660 169999814
848937385843 8 7 17 19 0 5 6 2
567365141997043401 3960606 1985068 4125828 5630794 76825921 901167353 889742167 772908548
1783585506 9999987 1 10000000 999999 990000001 79999998 868999132 81999927
523223149082128364 158568 991720 2994044 1181676 376610494 650869357 336623539 620070320
967702028973969107 1 10000000 10000000 10000000 840000001 670000000 40000001 19999998
13 5 7 5 9 1 3 2 5
499587295797208700 3469541 1730417 5070929 1825598 855537260 882995491 898204830 34203727
1708396388 999999 12347 9699690 9748872 727477719 669281518 799407527 906645153
80933573 102400 15000 9699690 9748872 989369349 872975008 916394050 370457193
940978906345340844 759324 967048 10000000 9999999 810000001 650000000 59999995 259999974
991127410199121019 123456 557 9988776 1025 39955758 719192622 152456585 350827775
1606423995 9999909 9999991 9999949 10000000 499997451 929995254 810000001 970000002
960043019846431759 9999909 9999991 9999949 9999991 879995513 99999488 349999686 549999505
70413132 123 1 10000000 10000000 20000001 190000000 90000001 360000002
859373750084 8 7 17 19 1 16 6 2
3 1 3 3 3 1 0 1 1
1555193042 9999991 1 9999991 9999989 259999767 19999980 239999737 679999252


6分钟之内根本算不出来阿，请教要用什么算法？

btdm123

918495108443110920 9999991 1 9999991 9999989 849999236 589999466 309999660 169999814
这一行就出不来了，lcm(9999991, 9999991)=99999800000099, 也忒恐怖了