using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/2758 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("5 3"); WillReturn.Add("2 6 7 19 14"); WillReturn.Add("1 4 2"); WillReturn.Add("3 5 4"); WillReturn.Add("1 5 7"); //2 //0 //2 } else if (InputPattern == "Input2") { WillReturn.Add("5 4"); WillReturn.Add("7 6 5 4 3"); WillReturn.Add("1 5 2"); WillReturn.Add("2 3 3"); WillReturn.Add("2 4 4"); WillReturn.Add("1 3 5"); //2 //1 //1 //1 } else if (InputPattern == "Input3") { WillReturn.Add("3 1"); WillReturn.Add("1000 1000 100"); WillReturn.Add("1 3 10"); //3 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray(); // IndのList[Aの約数]なDict var IndListDict = new Dictionary>(); for (long I = 0; I <= AArr.GetUpperBound(0); I++) { long[] YakusuuArr = DeriveYakusuuArr(AArr[I]); foreach (long EachYakuu in YakusuuArr) { if (IndListDict.ContainsKey(EachYakuu) == false) { IndListDict[EachYakuu] = new List(); } IndListDict[EachYakuu].Add(I); } } long[] wkArr = { }; Action SplitAct = pStr => wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray(); var sb = new System.Text.StringBuilder(); foreach (string EachStr in InputList.Skip(2)) { SplitAct(EachStr); long RangeSta = wkArr[0] - 1; long RangeEnd = wkArr[1] - 1; long K = wkArr[2]; if (IndListDict.ContainsKey(K) == false) { sb.Append(0); } else { long Answer = GetListRangeValueCnt.GetCnt(IndListDict[K], RangeSta, RangeEnd); sb.Append(Answer); } sb.AppendLine(); } Console.Write(sb.ToString()); } // 約数を列挙する static long[] DeriveYakusuuArr(long pTarget) { var YakusuuSet = new HashSet(); for (long I = 1; I * I <= pTarget; I++) { if (pTarget % I == 0) { YakusuuSet.Add(I); YakusuuSet.Add(pTarget / I); } } long[] YakusuuArr = YakusuuSet.ToArray(); Array.Sort(YakusuuArr); return YakusuuArr; } } #region GetListRangeValueCnt // 昇順にソートされたList、Min,Maxを引数とし、 // Min以上Max以下な値の個数を返す internal class GetListRangeValueCnt { static internal long GetCnt(List pSortedList, long pMinVal, long pMaxVal) { if (pMinVal > pMaxVal) { throw new Exception("pMinVal > pMaxVal"); } int ResultInd1 = ExecNibunhou_LowerBound(pMinVal, pSortedList); int ResultInd2 = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedList); if (ResultInd1 == -1 || ResultInd2 == -1) return 0; return ResultInd2 - ResultInd1 + 1; } // 二分法で、Val以上で最小の値を持つ、添字を返す static int ExecNibunhou_LowerBound(long pVal, List pList) { if (pList.Count == 0) return -1; // 最後の要素がVal未満の特殊ケース if (pVal > pList[pList.Count - 1]) { return -1; } // 最初の要素がVal以上の特殊ケース if (pVal <= pList[0]) { return 0; } int L = 0; int R = pList.Count - 1; while (L + 1 < R) { int Mid = (L + R) / 2; if (pList[Mid] >= pVal) { R = Mid; } else { L = Mid; } } return R; } // 二分法で、Val以下で最大の値を持つ、添字を返す static int ExecNibunhou_LowerOrEqual_Max(long pVal, List pList) { if (pList.Count == 0) return -1; // 最後の要素がVal以下の特殊ケース if (pVal >= pList[pList.Count - 1]) { return pList.Count - 1; } // 最初の要素がVal超えの特殊ケース if (pVal < pList[0]) { return -1; } int L = 0; int R = pList.Count - 1; while (L + 1 < R) { int Mid = (L + R) / 2; if (pList[Mid] <= pVal) { L = Mid; } else { R = Mid; } } return L; } } #endregion