https://ac.nowcoder.com/acm/contest/6290/E
由题目给出的式子可知,这道题要分为两个部分来计算。
首先我们来看看啊 “a[]/x” 这一部分
我们先预处理出在范围内的所有数字的出现次数,计算出前缀和
然后计算出每一个倍数范围内的数字个数(因为要取整,所以这样做)
再乘以这个倍数即可
再来看看另一部分
用a【】来储存预处理出有倍数关系的次数;
然后计算的时候,我们就依次前缀和相加即可
举个例子 比如n=1,m=4,val[1]=2
那么当x=1时,ans为0
当x=2时,ans为1
当x=3时,ans为1
当x=4时,ans为2
那么,我们的预处理数组在处理的时候呢,就是a【1】= 0
a【2】= 1
a【3】= 0
a【4】=1
前缀和相加之后,就能得出上面的结果
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int n,m,V[2000005]={0},S[2000005]={0}; 5 long long t,ans=0,a[2000005]={0}; 6 int main() 7 { 8 int i,j,l,r; 9 scanf("%d%d",&n,&m); 10 for(i=1;i<=n;i++)scanf("%d",&j),V[j]++; 11 for(i=1;i<=m;i++) 12 { 13 S[i]=S[i-1]+V[i]; 14 for(j=i;j<=m;j+=i) 15 a[j]+=V[i]; 16 } 17 for(i=1;i<=m;i++) 18 { 19 a[i]+=a[i-1],t=a[i]; 20 for(j=i;j<=m;j+=i) 21 { 22 l=j,r=min(j+i-1,m); 23 t+=(long long)j/i*(S[r]-S[l-1]); 24 } 25 ans^=t; 26 } 27 printf("%lld\n",ans); 28 return 0; 29 }
原文链接: https://www.cnblogs.com/pangbi/p/13303010.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/365947
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!