Доброй ночи/рассвета/утра/дня/заката/вечера/ночи, Codeforces! Сегодня я заметил, что у меня задача С в Educational Codeforces Round 42 не прошла из-за теста 12334567891. Проверив свою программу я понял, что проблема была в проверке числа на квадрат, а именно if (sqrt(n) * sqrt(n) == n) это проверку я заменил на if (int(sqrt(n)) == sqrt(n)) и оно прошло все тесты. Можете сказать почему первая проверка не есть правильной.
Моё решение: http://codeforces.me/contest/962/submission/37171806
Обе проверки плохие, но во второй просто получаем погрешность в вычислении sqrt(n) и ничего с этим не делаем, а в первой мы ее делаем еще и в два раза больше из-за умножения.
Спасибо. А как можно проверять без погрешности, если это возможно.
Можно так:
int n = 2147483647; // WAint n = 2147483646; // TLEUPD: https://ideone.com/Wl12Mf
Никто не запрещал использовать long long, если есть необходимость
понятно, что тема старая, но вот зачем использовать 2 цикла while не совсем понятно.. вообще вроде и без них всегда работает(если есть примеры где не работает, напишите их пожалуйста), а так можно использовать llrint:
int sqr = llrint(sqrt(n));
Ещё можно двоичным поиском.
Все стандартные функции процессора (в том числе и sqrt) имеют точность 10^(-14), чего более чем хватает для чисел до миллиарда.