Finding number of ordered pairs with a given property

Правка en8, от typedeftemplate, 2019-09-24 05:36:37

Given an integer 1 <= N <= 100, and 1 <= MIN, MAX <= 10^5, how can I compute the number of ordered pairs (a_1, a_2, ..., a_N) such that MIN <= a_i <= MAX for any i, and gcd(a_1, a_i) = 1 for any i not equal to 1?

For example, when N = 3, MIN = 2, and MAX = 4, the valid configurations are (2,3,3), (3, 2, 2), (3, 4, 2), (3, 4, 4), (4, 3, 3), and (3, 2, 4), so the output should be "6".

I am pretty sure (not 100%) this is a DP problem, but I can't manage to come up with the solution. Also, obviously, every configuration with the first number prime is valid, but this doesn't have to be the case. Does anyone have any ideas? I have been stuck on this problem for a few days now. Maybe I'm going about it wrong, and there is a really simple solution? Print the answer modulo 10^9 + 7.

Side-note: Is it possible to get TeX to work in these blogs?

Теги #dp, #combinatorics, #number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский typedeftemplate 2019-09-24 05:36:37 35 Tiny change: ' solution?\n\n\nSide' -> ' solution? Print the answer modulo 10^9 + 7. \n\n\nSide'
en7 Английский typedeftemplate 2019-09-24 05:35:10 50
en6 Английский typedeftemplate 2019-09-24 05:34:31 2 Tiny change: 'and MAX = 3, the vali' -> 'and MAX = 4, the vali'
en5 Английский typedeftemplate 2019-09-24 05:28:59 2 Tiny change: '2, ..., a_n) such tha' -> '2, ..., a_N) such tha'
en4 Английский typedeftemplate 2019-09-24 05:09:31 2 Tiny change: 'le to get LaTeX to wor' -> 'le to get TeX to wor'
en3 Английский typedeftemplate 2019-09-24 05:09:16 68
en2 Английский typedeftemplate 2019-09-24 05:08:31 116
en1 Английский typedeftemplate 2019-09-24 05:07:50 665 Initial revision (published)