A Hard Problem on Topcoder

Revision en1, by meaningIess, 2019-05-25 12:08:59

You are given a number $$$n$$$ and a set $$$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.|d|<=50 and n<=1e18. In Topcoder its called "HugeGraph". I have searched for the editorial and I found nothing. Please anybody gives a editorial? Btw, for n,|d|<=1e5, if the problem can be solved? Sorry for my bad english:)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English meaningIess 2019-05-25 12:08:59 508 Initial revision (published)