被3整除

using System;
public class DividedByThreeClass
    {
        /**
         * ACM链接：https://www.nowcoder.com/questionTerminal/00f3f6fc145b4d3ea5ab460f957ec8fc?orderByHotValue=0&questionTypes=000100&mutiTagIds=149&page=7&onlyReference=false
         * 小Q得到一个神奇的数列: 1, 12, 123,...12345678910,1234567891011...。
         * 并且小Q对于能否被3整除这个性质很感兴趣。
         * 小Q现在希望你能帮他计算一下从数列的第l个到第r个(包含端点)有多少个数可以被3整除。
         */
        // 别的语言过的了 C#时间上过不了的代码 有点奇怪 对数器校验是没错的
        private static long DividedByThreeNoPass( int l, int r )
        {
    
            long res = 0;
            for (long i = l; i <= r; i++) if ( (((1 + i) * i) >> 1) % 3 == 0  )res++;
            return res;
        }
        
        
        // 打表法
        // 直接找规律  可以发现从1开始三个是一组  为false true true
        
        // 求解1 - end上有多少个能被3整除 O(1)
        private static long CalNum(long end)
        {
            if (end < 1) return 0;
            long res = end / 3 * 2 ;
            long endNum = end % 3;
            if (endNum > 0) res += endNum - 1;
            return res;
        }
        
        private static long DividedByThree( long l, long r)
        {
            long num1 = CalNum(l - 1);
          long num2 = CalNum(r);
          return num2 - num1;
        }
        
        // 对数器
        private static void Test()
        {
            int testTime = 1000;
            int big = 1000000000;
            int bigLength = 1000;
            Random random = new Random();
            for (int i = 0; i < testTime; i++)
            {
                int l = random.Next(1, big);
                int length = random.Next(1, bigLength);
                int r = random.Next(l + length, big);
                long ans1 = DividedByThree(l, r);
                long ans2 = DividedByThreeNoPass(l, r);
                if (ans1 != ans2)
                {
                    Console.WriteLine( $"用例:[{l}, {r}]   结果不通过  OJ方法结果:{ ans1 }   超时方法结果:{ ans2 } " );
                    return;
                }
            }
            Console.WriteLine("超时方法校验通过");

        }

        public static void Main(string[] args)
        {
            // string input = Console.ReadLine();
            // if (input != null)
            // {
            //     string[] param = input.Split(' ');
            //     Console.WriteLine( DividedByThree(long.Parse(param[0]), long.Parse(param[1]))  );
            // }
            Test();
        }
    }