Сколькими способами 3600 можно разбить на произведение двух сомножителей?

PS
1*3600 не считается, 10*360 и 360*10 считается за одно

PPS
Ну вы поняли ... хоцца формулу для общего случая

Здравствуйте, Pushkin, Вы писали:

P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?

P>PS
P>1*3600 не считается, 10*360 и 360*10 считается за одно

P>PPS
P>Ну вы поняли ... хоцца формулу для общего случая

Халява. Счиатем делители. Пусть a(n) — кол-во простых чисел n в разложении числа на простые делители.
Если число n не простое, то a(n)=0.

Считаем производение по (n=2..N: a(n+1)).

Это кол-во неэлементарных делителей. Число пар равно половине (округление вверх).

Причина этого удивительного явления очевидна и ее осознвние оставляется как самостоятельно упражнение.

Здравствуйте, Pushkin, Вы писали:

P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?

P>PS
P>1*3600 не считается, 10*360 и 360*10 считается за одно

P>PPS
P>Ну вы поняли ... хоцца формулу для общего случая

Все весьма просто. Наше число N разлагается в произведение простых множителей:

N = p1^n1 * p2^n2 * ... * pm^nm

Тогда по набору коэффициентов i1...im получим

a = p1^i1 * p2^i2 * ... * pm^im
b = N / a
N = a*b

Таких различных а набирается ((n1+1)*(n2+1)*...(nm+1)) штук. Для учета симметричных случаев поделим это число на два и вычтем единицу для тривиального разложения.

Таким образом, разложений числа будет ((n1+1)*(n2+1)*...(nm+1))/2 — 1

M>Считаем производение по (n=2..N: a(n+1)).

Сорри. Произведение по a(n)+1, разумеется.

Здравствуйте, Pushkin, Вы писали:

P>Сколькими способами 3600 можно разбить на произведение двух сомножителей?

P>PS
P>1*3600 не считается, 10*360 и 360*10 считается за одно

P>PPS
P>Ну вы поняли ... хоцца формулу для общего случая

3600=2*5*2*5*3*2*3*2= 2^4 * 3^2 * 5^2

2 2 1800
3 3 1200
5 5 720
22 4 900
23 6 600
25 10 360
33 9 400
35 15 72
55 25 144
222 8 450
223 12 300
225 20 180
233 18 200
235 30 120
255 50 72
335 45 80
355 75 48
2222 16 225
2223 24 150
2225 40 90
2233 36 100
2235 60 60

Ответ: 22.

Да, ребята...голыми руками вас не возьмёшь...
Я всё-таки приведу формулу

(n1+1)*(n2+1)*...*(nk+1)/2
Здесь nk — степени простыхо множителей в разложении, а деление с округлением вниз (как в Си)

Для 3600=2^4*3^2*5^2
(4+1)*(2+1)*(2+1)/2=45/2=22

Ну раз вы такие умные, скажите, сколько разложений на ТРИ множителя?
(Различающиеся порядком считаем за одно)
И сколько ВСЕГО разложений (с любым количеством сомножителей)?

Здравствуйте, m.a.g., Вы писали:

MAG>Таких различных а набирается ((n1+1)*(n2+1)*...(nm+1)) штук. Для учета симметричных случаев поделим это число на два и вычтем единицу для тривиального разложения.

MAG>Таким образом, разложений числа будет ((n1+1)*(n2+1)*...(nm+1))/2 — 1

Для N=K^2 нужно округлять в большую сторону (поскольку разложение N=K*K будет сосчитано 1/2 раза, а должно быть 2/2).

Здравствуйте, Pushkin, Вы писали:



P>Ну раз вы такие умные, скажите, сколько разложений на ТРИ множителя?
P>(Различающиеся порядком считаем за одно)
P>И сколько ВСЕГО разложений (с любым количеством сомножителей)?
P>

Если я правильно понимаю, то столько же сколько и всевозможных разбиений в n — элементном множестве, где n — число простых делителей(с повторами), а это числа Стирлинга(вроде) и хорошей формулы для них нет. Только рекуррентная.