結果

問題 No.2592 おでぶなおばけさん 2
コンテスト
ユーザー chineristAC
提出日時 2023-12-20 00:32:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 658 ms / 2,500 ms
コード長 1,078 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 117,652 KB
最終ジャッジ日時 2024-09-27 09:36:23
合計ジャッジ時間 46,109 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 83
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations
from heapq import heappop,heappush
from collections import deque
import random
import bisect

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def is_prime(n):
    if n == 1:
        return False
    for d in range(2,n):
        if d * d > n:
            break
        if n % d == 0:
            return False
    return True

def random_prime(L,R):
    while True:
        x = random.randint(L,R)
        if is_prime(x):
            return x


T = 10
RP = [random_prime(10**8,10**9) for _ in range(T)]

N,Q,K = mi()
A = li()


cum = [[0]*(N+1) for t in range(T)]
for t in range(T):
    tmp_pow = 1
    mod = RP[t]
    for i in range(N):
        cum[t][i+1] = cum[t][i] + A[i] * tmp_pow
        cum[t][i+1] %= mod
        tmp_pow = tmp_pow * K % mod

for _ in range(Q):
    l,r = mi()
    l,r = l-1,r

    flg = 0
    for t in range(T):
        check = (cum[t][r] - cum[t][l]) % RP[t]
        if check != 0:
            flg = 1
    
    print("Yes" if flg else "No")
0