首页 > 其他分享 >Even Subarrays(数论问题)

Even Subarrays(数论问题)

时间:2022-12-31 20:22:54浏览次数:76  
标签:Even even XOR 数论 Subarrays number int test divisors

题目链接

题目描述:

You are given an integer array \(a_1,a_2,…,a_n (1≤a_i≤n).\)

Find the number of subarrays of a whose XOR has an even number of divisors. In other words, find all pairs of indices \((i,j) (i≤j)\) such that \(a_i⊕a_{i+1}⊕⋯⊕a_j\) has an even number of divisors.

For example, numbers \(2, 3, 5\) or \(6\) have an even number of divisors, while \(1\) and \(4\) — odd. Consider that 0 has an odd number of divisors in this task.

Here XOR (or \(⊕\)) denotes the bitwise XOR operation.

Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer.

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases \(t (1≤t≤10^4)\). Description of the test cases follows.

The first line of each test case contains a single integer \(n (2≤n≤2⋅10^5)\) — the length of the array \(a\).

The second line contains n integers \(a_1,a_2,…,a_n (1≤a_i≤n)\).

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2⋅10^5\).

输入描述:

For each test case, print the number of subarrays, whose XOR has an even number of divisors.

样例:

input:

4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

output:

4
11
0
20

AC代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int T = 1;
LL n;

void solve()
{
    scanf("%lld", &n);

    vector<int> a(n), b(2 * n); // 开两个vector,一个用于存数组,一个用于存某个数出现的次数

    a.clear(), b.clear();

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    LL cnt = 0; // 存储异或和的因数为奇数个的数的个数
    int t = 0;

    b[t]++; // a[0] ^ a[0]为0

    for (int i = 0; i < n; i++)
    {
        t ^= a[i];
        // cout << t << ' ';
        // n个数可能的异或最大值肯定小于2 * n
        // 判断某个数的因数是否为奇数的条件就是判断其是否是完全平方数
        for (LL j = 0; j * j < 2 * n; j++)
        {
            // 一个数 t 异或一个完全平方数的结果,该结果异或 t的结果必定是那个完全平方数
            if ((t ^ (j * j)) < 2 * n)
            {
                cnt += b[t ^ (j * j)]; // cnt 加上这个数出现过的次数

                cout << t << ' ' << j * j << ' ' << (t ^ (j * j)) << ' ' << cnt << '\n';
            }
        }

        b[t]++; // t的出现的次数加一
    }

    LL ans = (n * (n + 1) / 2) - cnt; // 总共的个数减去不成立的个数即为成立的个数

    printf("%lld\n", ans);
}

int main()
{
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    scanf("%d", &T);

    while (T--)
    {
        solve();
    }

    return 0;
}

标签:Even,even,XOR,数论,Subarrays,number,int,test,divisors
From: https://www.cnblogs.com/KSzsh/p/17017080.html

相关文章

  • Algorithm 2 - 一些数论/组合计数知识
    0.一些前置知识莫比乌斯函数:定义\(\mu(x)\)为:当\(x\)含平方因子,则\(\mu(x)=0\);否则设其有\(p\)个质因子,\(\mu(x)=(-1)^p\)。特别的,\(\mu(1)=1\)。莫比乌斯......
  • EventLog Analyzer中的综合日志收集
    日志管理的第一步是收集日志数据。日志收集可能是一项具有挑战性的任务,因为某些系统(例如,防火墙、入侵检测系统和入侵防御系统)会生成大量日志数据的EPS(每秒事件数)。无论日志......
  • WPF中使用EventHandler更新UI内容
    在WPF中,EventHandler类似于一套订阅与发布的操作。甲方提供一个event的回调注册入口让乙方来订阅自己发布的event。这么理解起来就是需要发布消息的一方定义event(就像是C语......
  • Qt学习笔记(一) 关于QWidget类的paintEvent方法
      今天要讨论的也算是QT的核心之一了,那就是如何对widget进行重绘,这里就是可以看到,继承了QWidget的子类,自己重新写一个paintEvent函数就可以了。这个paintEvent就相当......
  • window.onerror 和window.addEventListener('error')的区别
    1.定义window.onerror全局事件函数window.onerror=function(message,source,lineno,colno,error){...}/**message:错误信息(字符串)。可用于HTMLonerror="......
  • python3.7导入gevent模块报错的解决方案
    pip3install-U--force-reinstall--no-binary:all:gevent附上参数说明-U,--upgradeUpgradeallspecifiedpackagestothenewestavailableversion.Thehand......
  • VueJS使用addEventListener的事件如何触发执行函数的this
    1、使用浏览器监听切屏为例此处为考虑浏览器兼容性推荐使用:document.addEventListener1.1、正常函数使用如下:letn=0;letmax=3;//切屏最大次数document.addE......
  • the seventh——2022.12.28
    %a.bf的含义%f是输出float(单精度浮点型)型变量,%m.nf中m代表输出数长,n代表小数点后的数长,即保留n位小数。如果小数点后的数大于n,例如12.4567按照%5.2f输出得12.46(四舍五入......
  •   Codeforces Round #841 (Div. 2) and Divide by Zero 2022 -----C. Even Subarray
    题目链接:https://codeforces.com/contest/1731/problem/C  题目的大致意思是:给长度为n的数组,求 子数组的异或和  的结果的除数个数为偶数个的子数组有多......
  • C. Even Subarrays
    CodeforcesRound#841(Div.2)andDividebyZero2022题目大意给定一个数组,求满足所有元素异或的结果有偶数个因子的子数组的个数。本题将0视作有奇数个因子。解题......