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).

Auto comment: topic has been updated by ChuVanKhanh (previous revision, new revision, compare).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.

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 ?

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.