Блог пользователя ChuVanKhanh

Numerical Analysis
Автор ChuVanKhanh, история, 20 месяцев назад, По-английски

Hi everyone, I've encountered a rather difficult problem for me, I hope you guys can give me some suggestions. The problem is as follows for a positive integer S (S <= 1e9), find how many ways to decompose the number S into the sum of positive integers whose greatest common divisor is 1.(Two sets of numbers that are vin permutations are also counted as different).

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
20 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Find a formula for the number of ways to write S as sum of positive integers.

Then find the number of ways to write S as a set of positive integers whose gcd is a multiple of d. (Note every element will have to be a multiple of d.)

Then obtain the answer by inclusion-exclusion.

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell more about ( Then find the number of ways to write S as a set of positive integers whose gcd is a multiple of d. (Note every element will have to be a multiple of d.) ?; What is d ?

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      d is any divisor of S.

      The idea is: suppose S = 36.

      Find the number of ways to write S as the sum of positive integers.

      Then find the number of ways to write S as the sum of multiples of 2, and then subtract that from the original count. (Because the gcd will be a multiple of 2 and we should not count it.)

      Do the same for multiples of 3.

      But then we have to add back the multiples of 6.

      → Ответить