using System;

using System.Numerics;

​

public static class MathExt

{

    public static BigInteger Sqrt(this BigInteger n)

    {

        if (n == 0) return 0;

        if (n > 0)

        {

            int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));

            BigInteger root = BigInteger.One << (bitLength / 2);

​

            while (!isSqrt(n, root))

            {

                root += n / root;

                root /= 2;

            }

​

            return root;

        }

​

        throw new ArithmeticException("NaN");

    }

​

    private static Boolean isSqrt(BigInteger n, BigInteger root)

    {

        BigInteger lowerBound = root*root;

        BigInteger upperBound = (root + 1)*(root + 1);

​

        return (n >= lowerBound && n < upperBound);

    }

}

​

public class BaseX

{

    private BigInteger m_Base = 0;

    private BigInteger m_Value = 0;

    private int m_Elements = 0;

    private BigInteger[] m_BaseElements = null;

​

    public BaseX(BigInteger baseValue)

    {

        m_Base = baseValue;

    }

    public BigInteger Base

    {

        get { return m_Base; }  

    }

    public BigInteger Value

    {

        get { return m_Value; }

        set { m_Value =value; Eval(); }

    }

    public BigInteger[] Elements

    {

        get { return m_BaseElements; }  

    }

    private void Eval()

    {

        // work through the value

        // We have to count up and find the upper limit

        m_Elements = -1;

        BigInteger Limit = 1;

        BigInteger Remainder = 0;

        Console.WriteLine("Finding Limit");

        while(Limit != 0)

        {

            m_Elements++;

            BigInteger powBase = BigInteger.Pow(m_Base, m_Elements);

            Limit = BigInteger.DivRem(m_Value, powBase, out Remainder);

            Console.WriteLine("Limit:{0} Remainder:{1} PowBase:{2} Elements: {3}", Limit, Remainder, powBase, m_Elements);

        }

        m_Elements -= 1;

        Console.WriteLine("Total Elements needed: {0}", m_Elements);

        // At this point we need to allocate the base elements

        m_BaseElements = new BigInteger[m_Elements];

        Remainder = m_Value;

        Console.WriteLine("Evaluating {0} to base {1}", m_Value, m_Base);

        // Now we have to count down from the number of elements

        for(int exponent = m_Elements - 1; exponent != -1; exponent--)

        {

            int exp = exponent + 1;

            m_BaseElements[exponent] = BigInteger.DivRem(Remainder, BigInteger.Pow(m_Base, exp), out Remainder);

            if( m_BaseElements[exponent] == 0 && exponent == 0)

            {

                m_BaseElements[exponent] = Remainder;   

            }

            Console.WriteLine("Remainder: {0} BaseValue[{1}]: {2}", Remainder, exponent, m_BaseElements[exponent]);

        }

    }

}

public class Program

{

    public static void Main()

    {

        BigInteger P = 251, Q = 151;

        BigInteger N = P * Q;

        BaseX basis = new BaseX(50);

        basis.Value = N;

        BigInteger total = 0;

        foreach(BigInteger element in basis.Elements)

        {

            total += element;

        }

        Console.WriteLine("Total:{0} P1:{1} Q:{2}", total, P, Q);

    }

}