412. Пи

Задано произвольное множество целых чисел. Вероятность того, что выбранная наугад пара чисел из этого множества не имеет общего делителя, равна 6 / p². По заданному множеству найти приближенное значение константы p.

Вход. Первая строка каждого теста содержит количество чисел n во множестве. Далее следуют n целых чисел, каждое из которых находится в промежутке от 0 до 32768. Последний тест содержит n = 0 и не обрабатывается.

Выход. По входным данным вычислить приблизительно значение p и вывести его с 6 знаками после запятой. Если p оценить не возможно (не существует ни одной взаимно простой пары в исходном множестве), то вывести сообщение ‘No estimate for this data set.’.

Пример входа

5
2
3
4
5
6
2
13
39
0
 

Пример выхода

3.162278
No estimate for this data set.
 

РЕШЕНИЕ

полный перебор

Анализ алгоритма

Вероятность того, что выбранная наугад пара чисел не имеет общего делителя, равна отношению количества взаимно простых пар common к общему количеству пар pairs. То есть common / pairs = 6 / p². Откуда . Остается перебрать все пары чисел, вычислить их наибольший общий делитель и подсчитать значения common и pairs.

Пример

В первом тесте входное множество состоит из чисел 2, 3, 4, 5, 6. Из этих пяти чисел можно составить 10 всевозможных пар: (2, 3), (2, 4), …, (5, 6). Шесть из десяти пар не имеют общих делителей: (2, 3), (2, 5), (3, 4), (3, 5), (4, 5), (5, 6). Откуда = 3.162278.

Реализация алгоритма

Функция вычисления наибольшего общего делителя gcd имеет вид:

int gcd(int i, int j)

{

return (i) ? gcd(j % i, i): j;

}

Читаем количество чисел n во входном множестве. Само множество заносим в массив m.

while(scanf("%d",&n), n)

{

for(i = 0; i < n; i++) scanf("%d",&m[i]);

Перебираем все возможные пары чисел множества (m[i], m[j]), 0 £ i < n – 1, i + 1 £ j < n. В переменной pairs подсчитываем общее число таких пар, в переменной common – число взаимно простых пар.

pairs = common = 0;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

{

pairs++;

if (gcd(m[i],m[j]) == 1) common++;

}

Если не существует ни одной взаимно простой пары (common = 0), то выводим сообщение о невозможности оценить p. Иначе значение p вычисляем по выше приведенной формуле и выводим с 6 знаками после запятой. Чтобы при делении избежать потери точности следует один из множителей числителя (например pairs) перевести в тип double.

if (!common) {printf("No estimate for this data set.\n"); continue;}

res = sqrt(6*(double)pairs/common);

printf("%.6lf\n",res);

}