JOIN

 Problem Statement

Problem Statement for HugeGraph

### Problem Statement

Cat Snuke has drawn a huge graph. You are given a long n and a long[] d that describe the graph. The graph has n vertices, numbered 0 through n-1. Vertices i and j are connected by an edge if and only if |i-j| is an element of d. Return the number of connected components of this graph.

### Definition

 Class: HugeGraph Method: countComponents Parameters: long, long[] Returns: long Method signature: long countComponents(long n, long[] d) (be sure your method is public)

### Constraints

-n will be between 2 and 10^18, inclusive.
-d will contain between 1 and 50 elements, inclusive.
-Each element of d will be between 1 and n-1, inclusive.
-Elements of d will be pairwise distinct.

### Examples

0)

 `5` `{2}`
`Returns: 2`
 The graph will look as follows: There are two connected components in this graph: {0, 2, 4} and {1, 3}.
1)

 `6` `{2, 3}`
`Returns: 1`
2)

 `10` `{6, 8, 9}`
`Returns: 3`
3)

 `100` `{10, 20, 30, 40, 50, 60, 70, 80, 90}`
`Returns: 10`
4)

 `33` `{30, 29, 26, 15}`
`Returns: 5`
5)

 `808` `{195, 774, 788, 781, 723}`
`Returns: 71`
6)

 `47933736652472` `{47932970752927, 47933439462262, 2570167893116, 47933306684356, 47931823444952}`
`Returns: 2566761627725`
7)

 `45466964736857613` ```{33250482667239488, 37822264384529608, 40095838646694298, 43479356281340667, 35203783529829951, 40580747920061306, 43377164971019776, 39064579296221318, 40001593684678420, 33451277901601382, 40995812050106167, 37014304154501058, 17759267713188789, 36704554868973353}```
`Returns: 3274732884432575`
8)

 `927386907126310589` ```{748147148561484840, 701393167746858761, 769696254000454180, 704972921953280463, 759946249333871738, 884450289438010670, 746985782208205106, 774136608403627034, 340934288037171102, 842771692796482305, 781200159564662404, 714890479593837724, 692135607544998078, 869198777483846839, 857427314409450650, 769959320733418646, 834561823397164073, 859931184678488658, 772342405210344280, 884209280453229287, 742707070877737742, 713634305824576668, 885018270712907537, 774793793947310152, 742703922481466469, 903242244337866282, 891008000483677106, 811279910869615440, 741113236129095213, 739459726110363505, 762358705144212813, 830373753788440496, 908779619221983459, 887664283422679667, 759617794878713552, 910640611592949081, 783409949952075625, 863540471792847786, 927341859483997999, 836772868602095563, 698935183681576178, 862350615052508395, 878270753526059153, 702073460709372995, 699733226194776258, 695875778245571985, 827812810943605830, 873126653781760917, 889807390074772165, 897362441882835952}```
`Returns: 95415956985202718`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Special Round Match 600.5 Round 1 - Division I, Level Two