牛客练习赛29: F. 算式子

版权声明：本文为博主原创文章，你们可以随便转载 https://blog.csdn.net/Jaihk662/article/details/83188634

 

链接：https://www.nowcoder.com/acm/contest/211/F
来源：牛客网
 

题目描述

给定  个整数  。保证  。

对于每个  ，求出 。为了避免过量输出，你只需要将所有的 m 个结果异或起来输出。

输入描述:

第一行两个整数  。

第二行  个整数，第  个表示  。

输出描述:

一行一个整数，表示所有结果异或起来的结果。

输入

2 2
1 2

输出

0

 

思路：

算一下每个a[i]/x的贡献和每个x/a[i]的贡献

然后就是类似于质数筛的过程，对于每个i∈[1, m]暴力它所有的倍数

复杂度O(mlnm)

 

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 1000000007
int sum[4005005];
LL ans[2005005], dx[4005005];
int main(void)
{
	LL now, bet;
	int n, m, i, x, j;
	scanf("%d%d", &n, &m);
	for(i=1;i<=n;i++)
	{
		scanf("%d", &x);
		sum[x]++;
	}
	for(i=1;i<=m*2;i++)
		sum[i] += sum[i-1];
	for(i=1;i<=m;i++)
	{
		for(j=1;j*i<=m;j++)
		{
			ans[i] += (LL)j*(sum[i*(j+1)-1]-sum[i*j-1]);
			dx[i*j] += (LL)j*(sum[i]-sum[i-1]);
			dx[i*(j+1)] -= (LL)j*(sum[i]-sum[i-1]);
		}
	}
	bet = now = 0;
	for(i=1;i<=m;i++)
	{
		now += dx[i];
		ans[i] += now;
		bet ^= ans[i];
	}
	printf("%lld
", bet);
	return 0;
}