牛客月赛 G-many sum（筛因子）

佚名 6年前 (2019-05-11) 随笔 2092人围观抢沙发百度已收录

many sum

链接：https://ac.nowcoder.com/acm/contest/879/G
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入描述:

第一行三个整数 N,A1,M

输出描述:

第一行一个整数，表示答案。

示例1

输入

复制

10 10 313

输出

复制

备注:

1≤N≤2×10^6,0≤A1,M<10^4
通过此题的同学，不妨来想一些如果N=2×107的时候该怎么做呢？




d|i为“d整除i”或“i被d整除”，可看作i%d==0，也就是需要找i所有的因子。
筛因子法利用逆向思维，枚举因子的倍数反向加入到i中。
一开始存表预处理1~n因子T了，这里找到直接加入Bi即可，一步到位。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int a[2000005],b[2000005];
 
int main()
{
    int t,k,i,j;
    ll n,m;
    scanf("%d%d%d",&n,&a[1],&m);
    for(i=2;i<=n;i++){
        a[i]=(a[i-1]+7*i)%m;
    }
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j+=i){    //筛因子
            b[j]+=a[i];
        }
    }
    ll ans=0;
    for(i=1;i<=n;i++){
        ans^=b[i];
    }
    printf("%lld\n",ans);
    return 0;
}