tuenti9.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Tuenti9
{
    class Program
    {
        static Dictionary<uint, uint> _primeCount = new Dictionary<uint, uint>();

        static void Main(string[] args)
        {
            var lines = File.ReadAllLines("submitInput.txt");
            var n = Convert.ToInt32(lines[0]);
            var result = "";
            for (int i = 0; i < n; i++)
            {
                var t = Convert.ToUInt32(lines[i + 1]);
                var testCase = Solve(t);
                result += "Case #" + (i + 1).ToString() + ": " + testCase + "\n";
                
                Console.Write("Case #" + (i + 1).ToString() + ": " + result + "\n");
            }
            File.WriteAllText("submitOutput.txt", result);
            Console.Read();
        }

        static List<uint> GetAllDivisors(UInt32 t)
        {
            var result = new List<uint>();
            uint d = 2;
            while (t != 1)
            {
                if (t % d == 0)
                {
                    result.Add(d);
                    t = t / d;
                    d = 2;
                }
                else d++;
            }

            return result;
        }

        static uint CountOnes(uint p, uint steps)
        {
            BigInteger bi = 0;
            uint count = 0;
            BigInteger incr = 0;

            for (int i = 0; i < steps; i++)
            {
                incr = incr * 10 + 1; 
            }

            do
            {
                bi = bi % p;
                bi = bi * (int)Math.Pow(10, steps) + incr;
                count += steps;
            } while (bi % p != 0);
            return count;
        }

        static uint GCD(uint a, uint b)
        {   
            while (b != 0)
            {
                var t = b;
                b = a % b;
                a = t;
            }

            return a;
        }

        static uint MCD(uint a, uint b)
        {
            return a * b / GCD(a, b);
        }

        private static string Solve(UInt32 t)
        {
            if (t == 1) return "1 0";

            var l = GetAllDivisors(t); 
            var n2 = l.Count(n => n == 2);
            var n5 = l.Count(n => n == 5);

            var n0 = Math.Max(n2, n5);
            l = l.Where(n => n != 2 && n != 5).ToList();

            var lstFactors = new Stack<uint>();

            while (l.Count > 0)
            {
                uint p = l[0];
                int np = l.Count(n => n == p);

                var pp = (UInt32)Math.Pow(p, np);

                uint steps = 1;
                if (p == 3)
                    steps = pp;

                if (!_primeCount.ContainsKey(pp))
                {
                    uint v = CountOnes(pp, steps);
                    _primeCount.Add(pp, v);
                }   

                lstFactors.Push(_primeCount[pp]);

                l = l.Where(n => n != p).ToList();
            }

            uint n1 = 1;

            if (lstFactors.Count > 0)
            {
                while (lstFactors.Count > 1)
                {
                    var v1 = lstFactors.Pop();
                    var v2 = lstFactors.Pop();
                    n1 = MCD(v1, v2);
                    lstFactors.Push(n1);
                }

                n1 = lstFactors.Pop();
            }

            return n1.ToString() + " " + n0.ToString();
        }
    }
}