Problem Statement

An arithmetic sequence of length n is a sequence of n numbers in which the difference between each pair of adjacent numbers is some constant delta. For example, the sequence 1,6,11,16 is an arithmetic sequence of length 4 with delta=5. Now, consider the infinite set

{ 1, 3, 4, 7, 8, 9, ... }
This set is of particular interest to mathematicians because it contains arbitrarily long arithmetic sequences for any delta, yet it contains no infinitely long arithmetic sequences. The set is contructed by keeping or dropping successive groups of positive integers according to the following pattern: keep one (1), drop one (2), keep two (3,4), drop two (5,6), keep three (7,8,9), drop three (10,11,12), and so on.

Given n and delta, your task is to find the earliest arithmetic sequence contained in the set that has the given length and delta. In other words, you should find the smallest number A such that all integers of the form A+i*delta are in the set, for all i between 0 and n-1, inclusive. You should return A.

Definition

 Class: ArithSeq Method: minStart Parameters: int, int Returns: long Method signature: long minStart(int n, int delta) (be sure your method is public)

Constraints

-n is between 2 and 30, inclusive.
-delta is between 1 and 100000000, inclusive.

Examples

0)

 3 3
Returns: 1
 The sequence is 1, 4, 7.
1)

 5 12
Returns: 9
2)

 6 12
Returns: 3661
3)

 30 4130
Returns: 1001001
4)

 30 100000000
Returns: 670380219057

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3455

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5870&pm=3455

vorthys

Testers:

PabloGilberto , lbackstrom , brett1479

Math