Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### meaningIess's blog

By meaningIess, history, 9 months ago, ,

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:)

• +9

 » 9 months ago, # |   0 I cannot search for this problem in Topcoder archive. Was this special round? If you know which srm it was you can check petr blog, I think he explains some problems from round he participated.
•  » » 9 months ago, # ^ |   0 Here is the address: https://arena.topcoder.com/index.html#/u/practiceCode/15833/33977/12832/1/319775
•  » » 9 months ago, # ^ |   0 If I know which SRM, I can found editorial on Google:(
•  » » » 9 months ago, # ^ |   0 SRM 600.5
•  » » » » 9 months ago, # ^ |   0 I can't found it. It seems that nobody write editorial for this contest:(
 » 9 months ago, # |   0 Maybe from big $n$ you can find the answer with Berlekamp-Massey?
•  » » 9 months ago, # ^ |   0 Ah, $d_i$ can be huge :(
•  » » 9 months ago, # ^ |   0 For big N, wouldn't the answer be just gcd?
•  » » » 9 months ago, # ^ |   0 Yes, i think if $n > 2 \cdot \max{d}$.
•  » » » 9 months ago, # ^ |   0 But what the answer will be when $n$ and $d_i$ both huge?
•  » » » » 9 months ago, # ^ |   0 Yeah, that's the question ;pI don't how to solve it. I only answered to 300iq's comment saying that BM is unnecessary.
•  » » » » » 9 months ago, # ^ |   0 For little $d_i$, it can be seemed $gcd$. For big $d_i$, it won't make a loop, every edge using big $d_i$ will minus the answer by 1? I guess that if all the $d_i>=n/2$ then the answer is $n - edges number$? I don't know if it's true.
 » 9 months ago, # |   0 Please, anybody replies? I neeeeeed the editorial! I'm VERY interested in this problem :(