Please help. Large integers

[stevanity]

I want to solve this problem.

There are 52735727364727372 students and 2889221271829121 teachers in a school . On children's day each teacher brings x toffees with him/her . All the toffees are collected and distributed equally to all the students . At the end it was found that there was exactly one toffee remaining .
What is the least possible value of x ?

I have the following code.
How do I handle large integers??

#include <iostream>
using namespace std;

int main()
{
    int children = 52735727364727372;
    int teachers = 2889221271829121;
    int no_of_chocholates=1;

    while(((no_of_chocholates*teachers)-1)%children!=0)
    {
        no_of_chocholates++;
    }
    cout<<no_of_chocholates;

    return 0;
}

[jonsca]

You're going to have to use either a char or an int array to hold the numbers.

ex 1234  =>  |1|2|3|4|

You'll have to write a procedure to do the multiplication and division digit by digit

Or if you can use a library, there's GMP or MPIR if you're using windows without cygwin

As a 2 minute exercise for your own benefit, find the largest values of a signed int and unsigned int (or look it up on wikipedia), you'll see these numbers are way over it.

[frogboy77]

would unsigned long long int(instead of int) suffice?

[jonsca]

Not supported under standard C++

error: ISO C++ does not support `long long'

I tried it with __int64 which is I believe is normally a Windows thing, but I think that the compiler substitutes long long for it.

I'm fairly certain the instructor is going for the array representation.

[stevanity]

You're going to have to use either a char or an int array to hold the numbers.

ex 1234  =>  |1|2|3|4|

You'll have to write a procedure to do the multiplication and division digit by digit

Or if you can use a library, there's GMP or MPIR if you're using windows without cygwin

As a 2 minute exercise for your own benefit, find the largest values of a signed int and unsigned int (or look it up on wikipedia), you'll see these numbers are way over it.

please help me out
im using codeblocks

how to do this??

is there a easier solution

[jonsca]

The easiest solution is to use the library that I gave, but if this is an assignment you need to do some variant on what I suggested above. Does it seem likely that this would be your instructors objective?

[stevanity]

The easiest solution is to use the library that I gave, but if this is an assignment you need to do some variant on what I suggested above. Does it seem likely that this would be your instructors objective?

dude its not an assignment. Its a math contest. There must be another way.
But this is also a way. So how do i solve this?

can u make a linear diophant equation of type ax+ by = n out of this problem??

[jonsca]

Is it project Euler? If it is, then there are usually some clever manipulations you can pull and the bottom falls out of the whole thing and you're left with the answer. I haven't made it very far through them, but some people around have.

I don't have any real experience with Diophantine Equations, so I couldn't tell you...

[frogboy77]

I think jonsca is correct, the answer seems too large to simply iterate through(be a little easy if so). I believe that there will be a clever mathematical shortcut.

It's not Euler but it's their kind of problem.

[stevanity]

please guyz
I have arrived with this equation.

2889221271829121X - 52735727364727372 Y = 1

X= number of chocolates each teach brings
and Y is the no of chocos each student gets.

[frogboy77]

Sorry Diophantine equations are beyond me. Perhaps you should try a math forum for more advice, then come here for help with the coding.

[-ordi-]

#include <stdint.h>

int pow(uint64_t b)
{
  int j = 2;
  // n ^ m, n ^ m + 1 ... n ^ (m - 2)
  for (int i = 2; i < b; i++)
  {
    j += j;
  }
  return j;
}

int main()
{
  int a, b;
  for (int i = a + 1; i < 63; i++)
  {
    int fd = pow(1ULL << i);
  }
  return 0;
}

[stevanity]

I found the result.
After solving the equation,
i got this solution
x = 52735727364727372 n+19245567719914049, n is integer [leaving out one chocolate]

so i need least x. So i put x=0
and i get answer as, 19245567719914049 which is perfectly divisible by 52735727364727372