JOIN
Get Time

   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