Using pow(x,y) in large numbers [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

I am inputting a number n where 1<=n<=10^5. I need a number of length n. So I use pow(10,n-1) but it doesnt work when n=100000. What is the error ?

EDIT: Its codeforces div2 round 152 problem B.

Chilly Willy wants to find the minimum number of length n, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.

A number's length is the number of digits in its decimal representation without leading zeros.

Input A single input line contains a single integer n (1 ≤ n ≤ 10^5).

My code works upto n=19. It fails on pretest 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;
}

Answer 1

Working with big numbers is not trivial; you cannot just use built-in types like int, double, long, etc for this. In order to calculate a number with 100000 digits, you need to have more than 300000 bits (a few kilobytes); this is in no way easy. Instead, you can print the answer without calculating it!

Saying that a number num is divisible by 2, 3, 5 and 7 is the same as num % 210 == 0. So the answer to your question looks like this:

100000000000... (really many zeros) ...00000xy0

All you need is to find two digits x and y, and print the above "number".

So you have to calculate pow(10, 99999) % 210 without calculating pow(10, 99999). To do it, start with pow(10, 0) = 1 and multiply by 10 successively:

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

After you calculate pow(10, 99999) % 210 in this manner (suppose it's xyz), adding 210 - xyz will make the number divisible by 210. So, to output the answer, print 1, then print 99996 times 0, then print 210 - xyz.

Answer 2

For typical 32 and 64 bit floating point data types (float and double), they are constrained to the range:

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)

A number with 100000 digits is waaaay outside the range of these datatypes. Hence, it fails (in some way), though you haven't told us how it fails.