题解 | many sum #

$[数学+思维]$

给定 $a_{1},n,m$ ，以及 $a$ 数组的递推式： $a_{i} = (a_{i-1}+7\times i) \%m,i\geq2$

定义 $b_{i} = \sum_{d | i}^{}{a_{d}}$ ， $d|i$ 的意思是 $i$ 能被 $d$ 整除，或者说 $d$ 是 $i$ 的一个因子。

例如 $b_{1} = a_{1}$ ， $b_{2} = a_{1} + a_{2}$ ， $b_{3} = a_{1} + a_{3}$ ， $b_{4} = a_{1} + a_{2} + a_{4}$ ......

const int N = 2e6 + 10;
int n, a_begin, m;
int a[N], b[N];
signed main(){
    HelloWorld;
    
    cin >> n >> a_begin >> m;
    a[1] = a_begin;
    for(int i = 2; i <= N - 10; i ++) a[i] = (a[i - 1] + 7 * i) % m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j * j <= i; j ++){
            if(i % j == 0){
                b[i] += a[j];
                if(j * j != i) b[i] += a[i / j];
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = ans ^ b[i];
    cout << ans << endl;
    return 0;
}

比较容易写出代码，但是时间复杂度为 $O(n\sqrt{n} )$ ，会超时

原因在于计算 $b$ 数组时枚举每一个 $i$ ，然后 $\sqrt{i}$ 的时间复杂度找每一个 $i$ 的因子 $j$

优化：使用数倍法(埃氏筛思想)来计算 $b$ 数组：

反过来思考：不是枚举每一个 $i$ 找每一个 $i$ 的因子 $j$ ，而是对于每一个因子 $j$ 来枚举它的所有倍数 $i$ ，然后 $b[j]+=a[i]$

for(int i = 1; i <= n; i ++){
    for(int j = i; j <= n; j += i) b[j] += a[i];
}

时间复杂度：调和级数求和 $n\times (1 + \frac{1}{2}+ \frac{1}{3}+......+ \frac{1}{n - 1}+ \frac{1}{n})=nlogn$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 2e6 + 10;
int n, a_begin, m;
int a[N], b[N];

signed main(){
    HelloWorld;
    
    cin >> n >> a_begin >> m;
    a[1] = a_begin;
    for(int i = 2; i <= n; i ++) a[i] = (a[i - 1] + 7 * i) % m;
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j += i) b[i] += b[j];
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) ans = ans ^ b[i];
    cout << ans << endl;
    return 0;
}