a250.
NCPC2011 Problem H Special Subsequences

Content

**Problem H**

**Special Subsequences**

Input File: ph.in

Time Limit: 5 seconds

Given a sequence of n integers x_{1},x_{2, …,} x_{n}_{ }and an integer k, 1≦k≦n,

we want to know if there exists a consecutive subsequence x_{i },x_{i+1, …,} x_{j} for

some i and j, 1≦i≦j≦n, such that the sum

Is divisible by k or not.

For example, let n = 7 and k = 6. In the sequence of 7 integers.

2,5,1,-4,5,9,3

The sum of the following consecutive subsequences can be divisible by k = 6.

1. i = 2, j = 3: 5+1 = 6,

2. i = 1, j = 6: 2+5+1-4+5+9 = 18,

3. i = 6, j = 7: 9+3 = 12,

We are going to write a very efficient program to solve the problem with

large numver of integers in a short span of time. It is required to print only

one particular solution, not all solutions. The solution we want to print is the

first such subsequence. The first solution is the one with the smallest value

of i. In the above example, the answer we want is i = 1 and j = 6. If there

are more than one solution with the same value of i, we want the one with

smallest valu of j.

Input

An instance of the problem consists of

1. the number of integers n,

2. the sequence of integer x_{i }, 1 ≦i≦n, and

3. the divisor k.

These data are stored in +2 lines in the input file.

1. The first line is the integer n.

2. The following is lines are the n integers x_{i }, 1≦i≦n. Each line

contains at most 20 integers.

3. The last line is the integer k.

In this problem, we assume that 1≦ n ≦100000, and -2^{30} ≦ x_{i }≦ 2^{30}.

Note that the test data file may contain more than one instances. The last

instance is followed by a line containing a single 0.

在此將題目修改 1 ≦ k ≦ 2147483647, 並且將所有數字排在同一行並不會切割

Output

The outputs for each test case are the two integers i and j which are the indexes of

the consecutive subsequence whose sum is divisible by k. Print exactly one space

between i and j. If there are no solution print “no solutions.”

Sample Input
#1

7 2 5 1 -4 5 9 3 6 10 11 -3 1 13 -5 6 1 -8 -4 5 10 0

Sample Output
#1

1 6 5 9

測資資訊：

記憶體限制：
512
MB

公開 測資點#0 (100%): 5.0s , <10M

公開 測資點#0 (100%): 5.0s , <10M

× 求序列最小的區間總和可以被 k 整除