Sum of nearest prime distances

Revision en18, by harsha314, 2021-08-08 19:11:45

Given a graph of $$$N$$$ nodes . Each node $$$i$$$ has value $$$A[i]$$$ . There is a directed edge from node $$$i$$$ to node $$$j$$$ if $$$A[i]\ >\ A[j]$$$ and $$$|i-j|\ \le\ K$$$ .

For every element , $$$B[i]$$$ is shortest distance to a node with prime value , if there is no path to such node $$$B[i]\ =\ 0$$$ . Find the sum of all elements of $$$B$$$ modulo $$$10^9\ +\ 7$$$ .

Constraints :

$$$1 \le K\le N\ \le 10^5\newline $$$ $$$B[i]\le\ 10^6\ \ \ \ \forall\ 1 \le i \le N$$$

Example :

  • $$$N=1 , K=1 , A\ =\ [1]\newline$$$ $$$B = [0]$$$
  • $$$N=3 , K=1 , A\ =\ [1,2,4]\newline$$$ $$$B = [0,0,1]$$$

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en24 English harsha314 2021-08-08 19:17:38 0 (published)
en23 English harsha314 2021-08-08 19:17:17 81
en22 English harsha314 2021-08-08 19:16:27 17
en21 English harsha314 2021-08-08 19:15:33 28
en20 English harsha314 2021-08-08 19:14:46 120
en19 English harsha314 2021-08-08 19:12:25 8 Tiny change: '=\ [1,2,4]\newline$\n$B = [0' -> '=\ [1,2,4]$\n$B = [0'
en18 English harsha314 2021-08-08 19:11:45 38
en17 English harsha314 2021-08-08 19:10:33 12
en16 English harsha314 2021-08-08 19:10:10 110
en15 English harsha314 2021-08-08 19:08:17 9
en14 English harsha314 2021-08-08 19:07:33 3 Tiny change: ':\n\n$1\leK\leN\ \le\ 10^5\newl' -> ':\n\n$1\le K\le N\ \le 10^5\newl'
en13 English harsha314 2021-08-08 19:07:09 7 Tiny change: '> :\n\n$1\ \le\ K\ \le N\ \le\ 10' -> '> :\n\n$1\leK\leN\ \le\ 10'
en12 English harsha314 2021-08-08 19:06:41 7 Tiny change: '\le\ 10^5\ $\n$\ B[i' -> '\le\ 10^5\newline $\n$\ B[i'
en11 English harsha314 2021-08-08 19:06:23 8 Tiny change: 'e\ 10^6\ \tab\forall\ 1' -> 'e\ 10^6\ \ \ \ \forall\ 1'
en10 English harsha314 2021-08-08 19:05:26 9
en9 English harsha314 2021-08-08 19:04:38 15 Tiny change: '<b> :\n\n$N\ \le\ 10' -> '<b> :\n\n$1\ \le\ K\ \le N\ \le\ 10'
en8 English harsha314 2021-08-08 19:03:50 11 Tiny change: '\ 7$ .\n\nConstraints : $N\ \le\ 1' -> '\ 7$ .\n\n<b>Constraints<b> :\n\n$N\ \le\ 1'
en7 English harsha314 2021-08-08 19:03:18 2 Tiny change: '10^6\ \forAll\ 1\ \le' -> '10^6\ \forall\ 1\ \le'
en6 English harsha314 2021-08-08 19:02:57 28 Tiny change: ' \le\ 10^6$' -> ' \le\ 10^6\ \forAll\ 1\ \le\ i\ \le\ N$'
en5 English harsha314 2021-08-08 19:01:42 52 Tiny change: '9\ +\ 7$ .' -> '9\ +\ 7$ .\n\nConstraints : $N\ \le\ 10^5\ ;\ B[i]\ \le\ 10^6$'
en4 English harsha314 2021-08-08 19:00:20 245
en3 English harsha314 2021-08-08 18:53:04 14 Tiny change: 'to node j \n$1\)\ \A[i] \>\ A[j]$ ' -> 'to node j if $A[i]\ >\ A[j]$ .'
en2 English harsha314 2021-08-08 18:52:28 1 Tiny change: 'ode j \n$1)\ \A[i] \' -> 'ode j \n$1\)\ \A[i] \'
en1 English harsha314 2021-08-08 18:52:08 129 Initial revision (saved to drafts)