P3794 签到题IV

    • 40通过
    • 315提交
  • 题目提供者Created_equal1 管理员
  • 标签 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    这场月赛好像其他题背景都很长,这题就不写背景了。

    题目描述

    给定一个长度为n的序列$a_1,a_2...a_n$,其中每个数都是正整数。

    你需要找出有多少对(i,j),$1 \leq i \leq j \leq n$且$gcd(a_i,a_{i+1}...a_j)~xor~(a_i~or~a_{i+1}~or~...~or~a_j)=k$,其中xor表示二进制异或,or表示二进制或。

    输入输出格式

    输入格式:

    第一行两个整数n、k。

    第二行n个整数$a_1,a_2...a_n$。

    输出格式:

    输出合法的(i,j)的对数。

    输入输出样例

    输入样例#1: 复制
    5 6
    2 4 3 4 2
    输出样例#1: 复制
    8

    说明

    对于30%的数据,$n \leq 500$。

    对于60%的数据,$n \leq 100000$。

    对于100%的数据,$1 \leq n,a_i \leq 500000$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。