How to solve spoj COPSEQ?
Difference between en3 and en4, changed 369 character(s)
Problem link: [Here](https://www.spoj.com/problems/COPSEQ/) 

 Harder version of problem: [Here](https://www.spoj.com/problems/COPSEQH/)↵

Abridged problem statement (for non-hard version):  ↵
Given **n <= 10^5** and **m <= 10^18**, how many sequence of length **n** satisfies the following conditions:   ↵
1.    Every number in the sequence is positive divisor of **m**  ↵
2.    Two adjacent element is not coprime.   ↵
Numbers can be repeated, different ordering counts as different sequence.↵

The best way I could think of right now is factorizing using pollard rho and then do O(N*D*Dnaive dp where D is number of divisors. Problem is D can be up to almost 10^5 for some highly composite numbers.↵

Another idea that comes to mind is to treat divisors as vertex, connect them if they can be adjacent in the resulting sequence, and find total number of walks with length (n-1) which can be done using matrix power. But this seems even slower because matrix can be large.↵

Any help is appreciated, thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Nanami_chan 2018-08-08 04:15:15 369 Tiny change: 'ersion):\nGiven $n <= 10^5\n' -> 'ersion):\n\nGiven **n** <= 10^5\n'
en3 English Nanami_chan 2018-08-07 17:28:13 33 Tiny change: 'em link: [here](https' -> 'em link: [Here](https'
en2 English Nanami_chan 2018-08-07 17:26:47 322
en1 English Nanami_chan 2018-08-07 04:30:37 320 Initial revision (published)