結果

問題 No.2758 RDQ
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-12 15:39:52
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 2,047 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 240 ms
コンパイル使用メモリ 96,112 KB
実行使用メモリ 145,664 KB
最終ジャッジ日時 2026-07-12 15:40:00
合計ジャッジ時間 5,484 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 6 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2758

import math

def main():
    N, Q = map(int, input().split())
    A = list(map(int ,input().split()))
    lrk = []
    for _ in range(Q):
        l, r, k = map(int, input().split())
        lrk.append((l - 1, r - 1, k))
    
    max_a = max(A)
    sqrt_a = int(math.sqrt(max_a))
    small_k_divisual_list = []
    for i in range(N):
        a = A[i]
        x_set = set()
        for k in range(1, sqrt_a + 1):
            if a % k == 0:
                x_set.add(k)
        small_k_divisual_list.append(x_set)
    
    # Mo's Algorithmで対応していく
    sqrt_n = int(math.sqrt(N))
    array = []
    for i in range(Q):
        l, r, k = lrk[i]
        l_index = l // sqrt_n
        array.append((l_index, r, l, k, i))
    array.sort(key=lambda x : x[0] * (2 * N) - x[1] )

    small_k_map = [0] * (sqrt_a + 1)
    large_k_map = [0] * (max_a + 1)
    for i in range(N):
        a = A[i]
        for k in small_k_divisual_list[i]:
            small_k_map[k] += 1
        large_k_map[a] += 1

    answers = [0] * Q
    left = 0
    right = N - 1

    def add(i, A):
        a = A[i]
        large_k_map[a] += 1
        for k in small_k_divisual_list[i]:
            small_k_map[k] += 1
    
    def delete(i, A):
        a = A[i]
        large_k_map[a] -= 1
        for k in small_k_divisual_list[i]:
            small_k_map[k] -= 1

    for _, r, l, k, index in array:
        while left < l:
            delete(left, A)
            left += 1
        while l < left:
            left -= 1
            add(left, A)

        while r < right:
            delete(right, A)
            right -= 1
        
        while r > right:
            right += 1
            add(right, A)

        if k <= sqrt_a:
            answers[index] = small_k_map[k]
        else:
            x = k
            while x <= max_a:
                answers[index] += large_k_map[x]
                x += k
    
    for i in range(Q):
        print(answers[i])

    


    

















if __name__ == "__main__":
    main()
0