Использование pow (x, y) в больших количествах
Я ввожу число n, где 1<= п<= 10 ^ 5. Мне нужен номер длины n. Поэтому я использую pow (10, n-1), но он не работает, когда n = 100000. В чем ошибка?
РЕДАКТИРОВАТЬ: его codeforces div2 раунд 152 задачи B.
Чилли Вилли хочет найти минимальное число длины n, такое, что оно одновременно делится на все числа, которые Вилли уже знает (2, 3, 5 и 7). Помоги ему с этим.
Длина числа — это количество цифр в десятичном представлении без начальных нулей.
вход
Одна строка ввода содержит одно целое число n (1 ≤ n ≤ 10 ^ 5).
Мой код работает до п = 19. Это не удается на предварительном тесте 9.
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int f=0;
unsigned long long n;unsigned long long out;
cin>>n;
unsigned long long num=1;unsigned long long lim=10;
for(unsigned long long z=0;z<n;z++)
{num=num*10;lim=lim*10;}num=num/10;lim=lim/10;
for(;num<lim;num++)
{
if((num%2==0)&&(num%3==0)&&(num%5==0)&&(num%7==0)){f=1;out=num;break;}
}
if(f==1){cout<<out;}
else if(f==0){cout<<"-1";}
return 0;
}
Решение
Работа с большими числами не тривиальна; Вы не можете просто использовать встроенные типы, такие как int, double, longи т. д. для этого. Чтобы вычислить число из 100000 цифр, вам нужно иметь более 300000 бит (несколько килобайт); это не так просто. Вместо этого вы можете распечатать ответ без расчета!
Сказать, что число num делится на 2, 3, 5 и 7 так же, как num % 210 == 0, Так что ответ на ваш вопрос выглядит так:
100000000000... (really many zeros) ...00000xy0
Все, что вам нужно, это найти две цифры x и y и напечатать вышеуказанное «число».
Так что вы должны рассчитать pow(10, 99999) % 210 без расчета pow(10, 99999), Для этого начните с pow(10, 0) = 1 и умножьте на 10 последовательно:
pow(10, 0) % 210 = 1
pow(10, 1) % 210 = (1 * 10) % 210 = 10
pow(10, 2) % 210 = (10 * 10) % 210 = 100
pow(10, 3) % 210 = (100 * 10) % 210 = (1000 % 210) = 160
pow(10, 4) % 210 = (160 * 10) % 210 = (1600 % 210) = 130
pow(10, 5) % 210 = (130 * 10) % 210 = (1300 % 210) = 40
...
После расчета pow(10, 99999) % 210 таким образом (предположим, что это xyz), добавляя 210 - xyz сделает число, делимое на 210. Итак, чтобы вывести ответ, выведите 1затем напечатайте 99996 раз 0затем распечатайте 210 - xyz,
Другие решения
Для типичных 32- и 64-битных типов данных с плавающей запятой (float а также double), они ограничены диапазоном:
float: 3.4E +/- 38 (that is, 3.4 * 10^(+/-38)) (with 7 digits of precision)
double: 1.7E +/- 308 (that is, 1.7 * 10^(+/-308)) (with 15 digits of precision)
Число с 100000 цифрами находится за пределами диапазона этих типов данных. Следовательно, это терпит неудачу (каким-то образом), хотя вы не сказали нам, как это терпит неудачу.