DIVSEQ - DIVSEQ
You're given two numbers - N and K (0 < N, K <= 1000). You have to count the number of sequences of positive integers with length N where every element must be not greater than K and for every two consecutive elements with indices i and i + 1 one of the conditions bellow must be true:
- a[i] is divisible by a[i + 1]
- a[i + 1] is divisible by a[i]
Input
On the only line you will be given the values of N and K.
Output
Print the number of the sequences described above modulо 1000000009.
Example
Input: 2 4 Output: 12
hide comments
vl4deee11:
2024-07-13 06:33:21
CHECK: scanf,printf - got RE, cin,cout - got AC |
|
cjn2007:
2021-09-28 08:24:30
Get Accepted in 1 go! : )
|
|
SUBHAM SANGHAI:
2017-04-04 12:27:34
Note, Mod is 10^9+9 not 10^9+7 |
|
rajat_jain21:
2017-04-04 08:09:45
I am getting a runtime error on test case 15. I cannot figure out where did i go out of bounds. Can someone help??
|
|
darryl:
2016-03-09 17:18:44
Then what about the condition about consecutive integers a[i] and a[i+1] that must be true? When N=1, no such consecutive integers exist so this condition cannot be true. |
|
ivo2001:
2016-03-09 10:49:10
Because when N = 1 every integer smaller or equal to K can be in the sequance so the answer is K
|
|
darryl:
2016-03-09 05:45:53
why when N=1, the answer is not 0? Last edit: 2016-03-09 05:46:39 |
|
quocanhvu:
2016-03-08 06:24:07
Here's a reword of the problem:
|
|
ivo2001:
2016-03-04 10:09:28
Explanation of the example:
|
|
ivo2001:
2016-03-04 10:00:25
You must count the number of sequences A of length N where 1<=A[i]<=K and for every two consecutive elements - A[i] and A[i + 1] must be true A[i] is divisible by A[i + 1] OR A[i + 1] is divisible by A[i]. Last edit: 2016-03-04 10:00:41 |
Added by: | ivokaragyozov |
Date: | 2016-03-03 |
Time limit: | 0.200s-0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | http://www.math.bas.bg/infos/files/2013-05-02-C1.pdf |