CoprimeNeighbors
SRM 706 · 2016-12-07 · by Errichto
Problem Statement
When little Limak played with numbers he noticed a surprising property: If two numbers are coprime, they like each other and want to spend time together. Otherwise, they hate each other and cannot be together. Limak has a good heart and he wants numbers to be happy.
You are given an
- Every element should be between 1 and 10^18, inclusive.
- Each pair of consecutive elements must be coprime. In other words, for every i between 0 and N-2, inclusive, the greatest common divisor of t[i] and t[i+1] must be 1.
- No other pairs of elements may be coprime. In other words, for every valid i and j such that i + 2 ⤠j the numbers t[i] and t[j] must have a common divisor greater than one.
Find any such sequence and return it as a
Constraints
- N will be between 2 and 500, inclusive.
2
Returns: {14, 25 }
We are looking for a sequence with 2 elements: t[0] and t[1]. The values t[0] and t[1] are supposed to be coprime. The values 14 and 25 are coprime, so {14, 25} is a valid sequence.
3
Returns: {1000000000000000000, 1, 1000000000000000000 }
Note that the sequence is not cyclic: the first element and the last element are not adjacent. For N=3 the numbers t[0] and t[2] cannot be coprime. Also note that the returned sequence may contain duplicates.
6
Returns: {14, 39, 80, 63, 26, 105 }
4
Returns: {172636023060370515, 218193726573364958, 71868480630185855, 584682195682971402 }
5
Returns: {172636023060370515, 218193726573364958, 71868480630185855, 584682195682971402, 29667137042210395 }
Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CoprimeNeighbors with a public method vector<long long> findAny(int N) · 23 test cases · 2 s / 256 MB per case