Matsoft :: Programs
biletul zilei cu meciuri din fotbal omnibet biletul zilei de azi la pariuri sportive
 
Home
|  
Company
|  
Products
|  
Carrers
|  
Programs
|  
Order
|  
Contact
|
 
using System;
using System.Collections.Generic;
using System.Collections;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    class IOHelper : IDisposable
    {
        StreamReader reader;
        StreamWriter writer;

        public IOHelper(string inputFile, string outputFile, Encoding encoding)
        {
            StreamReader iReader;
            StreamWriter oWriter;
            if (inputFile == null)
                iReader = new StreamReader(Console.OpenStandardInput(), encoding);
            else
                iReader = new StreamReader(inputFile, encoding);

            if (outputFile == null)
                oWriter = new StreamWriter(Console.OpenStandardOutput(), encoding);
            else
                oWriter = new StreamWriter(outputFile, false, encoding);

            reader = iReader;
            writer = oWriter;

            curLine = new string[] { };
            curTokenIdx = 0;
        }


        string[] curLine;
        int curTokenIdx;

        char[] whiteSpaces = new char[] { ' ', '\t', '\r', '\n' };

        public string ReadNextToken()
        {
            if (curTokenIdx >= curLine.Length)
            {
                //Read next line
                string line = reader.ReadLine();
                if (line != null)
                    curLine = line.Split(whiteSpaces, StringSplitOptions.RemoveEmptyEntries);
                else
                    curLine = new string[] { };
                curTokenIdx = 0;
            }

            if (curTokenIdx >= curLine.Length)
                return null;

            return curLine[curTokenIdx++];
        }

        public int ReadNextInt()
        {
            return int.Parse(ReadNextToken());
        }

        public double ReadNextDouble()
        {
            return double.Parse(ReadNextToken());
        }

        public void Write(string stringToWrite)
        {
            writer.Write(stringToWrite);
        }

        public void WriteLine(string stringToWrite)
        {
            writer.WriteLine(stringToWrite);
        }

        public void Dispose()
        {
            try
            {
                if (reader != null)
                {
                    reader.Dispose();
                }
                if (writer != null)
                {
                    writer.Dispose();
                }
            }
            catch { };
        }


        public void Flush()
        {
            if (writer != null)
            {
                writer.Flush();
            }
        }
    }


    public class MaxDequeue
    {
        LinkedList<Tuple<int, int>> elems = new LinkedList<Tuple<int, int>>();

        public void PushLast(int val, int curIdx)
        {
            var curElem = elems.Last;
            if (curElem == null)
            {
                elems.AddFirst(new Tuple<int, int>(val, curIdx));
            }
            else
                while (curElem.Value.Item1 < val)
                {
                    elems.RemoveLast();
                    curElem = elems.Last;
                    if (curElem == null)
                        break;
                }
            elems.AddLast(new Tuple<int, int>(val, curIdx));
        }

        public int PeekMax()
        {
            return elems.First.Value.Item1;
        }

        public void PopFirst(int curIdx)
        {
            if(elems.First.Value.Item2 <= curIdx)
                elems.RemoveFirst();
        }
    }

    class Program
    {
        protected IOHelper ioHelper;

        int n, k;

        List<int> primes = new List<int>();
        private bool[] isNotPrime;

        void DeterminePrimesUpTo(int upperLimit)
        {
            isNotPrime = new bool[upperLimit+1];

            int curCandidate = 3;

            primes.Add(2);

            isNotPrime[0] = true;
            isNotPrime[1] = true;

            while (curCandidate <= upperLimit)
            {
                if(!isNotPrime[curCandidate])
                    primes.Add(curCandidate);

                for (int coeff = 2; coeff*curCandidate <= upperLimit; coeff++)
                    isNotPrime[coeff*curCandidate] = true;

                curCandidate += 2;
            }

            isNotPrime = null;
        }

        private int[] divisorCount;

        private int[] coeffs;

        private int curPrimeIdx;
        private int curDivCount;
        private int curN;

        private bool direction;

        void enumerate()
        {
            while (curPrimeIdx >= 0)
            {
                if (curPrimeIdx >= primes.Count)
                {
                    divisorCount[curN] = curDivCount;
                    curPrimeIdx--;
                    direction = false;
                    continue;
                }

                var curPrime = primes[curPrimeIdx];
                int coeff = coeffs[curPrimeIdx];
                long nextN = curN;

                if (direction)
                { //just arrived from left or equivalent
                    if ((long) curN*(long) curPrime > n)
                    { //curPrime too large
                        divisorCount[curN] = curDivCount;
                        curPrime--;
                        direction = false;
                    }
                    else
                        curPrimeIdx++;
                }
                else
                {
                    if ((long) curN*(long) curPrime > n)
                    {//we're done with this prime for now
                        curDivCount /= (coeff + 1);
                        coeffs[curPrimeIdx] = 0;
                        curN /= (int)Math.Pow(curPrime, coeff);
                        coeff = 0;
                        curPrimeIdx--;
                        direction = false; //Back track one prime
                    }
                    else
                    {
                        curDivCount /= (coeff + 1);
                        coeff++;
                        coeffs[curPrimeIdx] = coeff;
                        curDivCount *= (coeff + 1);
                        curN *= curPrime;
                        direction = true; //advance to next prime
                    }
                }
            }
        }

        void ComputeDivisorCount()
        {
            divisorCount = new int[n+1];
            coeffs = new int[n + 1];
            curPrimeIdx = 0;
            curDivCount = 1;
            curN = 1;
            direction = true;
            enumerate();
        }
        
        public void Solve()
        {

            n = ioHelper.ReadNextInt();
            k = ioHelper.ReadNextInt(); //17176

            DeterminePrimesUpTo(n);
            ComputeDivisorCount();

            //ioHelper.WriteLine(primes[primes.Count - 1].ToString());
            //ioHelper.WriteLine(divisorCount[n].ToString());
            
            MaxDequeue myQueue = new MaxDequeue();

            int i;
            for(i = 1; i<=k;i++)
                myQueue.PushLast(divisorCount[i], i);

            long curSum = 0;
            for (i = 1; i <= n-k; i++)
            {
                var max = myQueue.PeekMax();
                curSum += max;

                myQueue.PopFirst(i);
                myQueue.PushLast(divisorCount[i+k],i+k);
            }

            curSum += myQueue.PeekMax();

            ioHelper.WriteLine(curSum.ToString());

            ioHelper.Flush();
            //Console.ReadKey();
        }

        public Program(string inputFile, string outputFile)
        {
            ioHelper = new IOHelper(inputFile, outputFile, Encoding.Default);
            Solve();
            ioHelper.Dispose();
        }

        static void Main(string[] args)
        {
            Program myProgram = new Program(null, null);
        }
    }
}

top