Submission #70244867

---

Source Code Expand

using System;
using System.Linq;
using CompLib.Util;
using System.Threading;
using System.IO;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
#if !DEBUG
        System.Console.SetOut(new System.IO.StreamWriter(System.Console.OpenStandardOutput()) { AutoFlush = false });
#endif
        int t = sc.NextInt();
        for (int i = 0; i < t; i++)
        {
            Query(sc);
        }

        Console.Out.Flush();
    }

    private long C, D;
    private string StrC;

    void Query(Scanner sc)
    {
        C = sc.NextLong();
        D = sc.NextLong();

        StrC = C.ToString();

        string strMin = $"{StrC}{StrC}";
        string strMax = $"{StrC}{C + D}";

        long ans = 0;

        for (int len = strMin.Length; len <= strMax.Length; len++)
        {
            long min;
            if (len == strMin.Length)
            {
                min = long.Parse(strMin);
            }
            else
            {
                min = long.Parse($"{StrC}0{new string('9', len - StrC.Length - 1)}");
            }

            long max = long.Parse($"{StrC}{new string('9', len - StrC.Length)}");

            // Console.WriteLine($"d2 {min}");

            long sqrtMin = IntSqrt(min);


            long sqrtMax = IntSqrt(max);

            // Console.WriteLine($"dd {sqrtMin} {sqrtMax}");

            long ok = sqrtMin;
            long ng = sqrtMax + 1;
            while (ng - ok > 1)
            {
                long mid = (ok + ng) / 2;
                if (OK(mid * mid, len)) ok = mid;
                else ng = mid;
            }

            ans += ok - sqrtMin;
        }

        Console.WriteLine(ans);
    }

    bool OK(long n, int len)
    {
        string strN = n.ToString();
        string strTop = strN.Substring(0, StrC.Length);
        string strBottom = strN.Substring(StrC.Length);
        if (strN.Length != len) return false;
        if (strTop != StrC) return false;

        if (long.Parse(strBottom) > C + D) return false;
        return true;
    }

    long IntSqrt(long n)
    {
        long ok = 0;
        long ng = (long)2e9;
        while (ng - ok > 1)
        {
            long mid = (ok + ng) / 2;
            if (mid * mid <= n) ok = mid;
            else ng = mid;
        }

        return ok;
    }


    public static void Main(string[] args) => new Program().Solve();
    // public static void Main(string[] args) => new Thread(new Program().Solve, 1 << 27).Start();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            if (_index >= _line.Length)
            {
                string s;
                do
                {
                    s = Console.ReadLine();
                } while (s.Length == 0);

                _line = s.Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public string ReadLine()
        {
            _index = _line.Length;
            return Console.ReadLine();
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public ulong NextULong() => ulong.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            string s = Console.ReadLine();
            _line = s.Length == 0 ? new string[0] : s.Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().AsParallel().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().AsParallel().Select(long.Parse).ToArray();
        public ulong[] ULongArray() => Array().AsParallel().Select(ulong.Parse).ToArray();
        public double[] DoubleArray() => Array().AsParallel().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().AsParallel().Select(decimal.Parse).ToArray();
    }
}

Submission Info

Judge Result