题意

给定n，求小于等于n的所有数中，因数和为自身的两倍的数有多少

限制：n 不大于500000

方法

质因子分解+预处理

一个整数只能被唯一质因数分解,设

$v=p_1^{a_1}{p}_2^{a_2}\cdots p_s^{a_s}v=p\_1^\{a\_1\}p\_2^\{a\_2\}\backslash cdots\; p\_s^\{a\_s\}$

那么$vv$的所有因数的和为

$(1+p_1+p_1^2+\cdots +p_1^{a_1})(1+p_2+p_2^2+\cdots +p_2^{a_2})\cdots (1+p_s+p_s^2+\cdots +p_s^{a_s})(1+p\_1+p\_1^2+\backslash cdots+p\_1^\{a\_1\})(1+p\_2+p\_2^2+\backslash cdots+p\_2^\{a\_2\})\backslash cdots(1+p\_s+p\_s^2+\backslash cdots+p\_s^\{a\_s\})$

注意到，且$p_2^{a_2}\cdots p_s^{a_s}p\_2^\{a\_2\}\backslash cdots\; p\_s^\{a\_s\}$的因数和为$(1+p_2+p_2^2+\cdots +p_2^{a_2})\cdots (1+p_s+p_s^2+\cdots +p_s^{a_s})(1+p\_2+p\_2^2+\backslash cdots+p\_2^\{a\_2\})\backslash cdots(1+p\_s+p\_s^2+\backslash cdots+p\_s^\{a\_s\})$

所以$vv$的因数的和可以由$p_2^{a_2}\cdots p_s^{a_s}p\_2^\{a\_2\}\backslash cdots\; p\_s^\{a\_s\}$的因数的和间接得到

例如样例的28

$28=2^2\cdot 728=2^2\; \backslash cdot\; 7$

因数和为$(1+2+2^2)(1+7)=(1+2+4)+(7+14+28)(1+2+2^2)(1+7)\; =\; (1+2+4)+(7+14+28)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
#define N 500000

ll mypow(ll v,ll pwr){ // 幂次计算
    ll r = 1;
    while(pwr){
        if(pwr%2)r*=v;
        v*=v;
        pwr/=2;
    }
    return r;
}

int main(){
    vector<ll> base(N+10,1); // 质数表
    vector<ll> sum(N+10,1); // 每个数的因数和
    vector<ll> ans(N+10,0); // 预处理答案
    rep(i,2,N+1){ // 初始化质数表
        if(base[i] != 1)continue;
        base[i] = i; // 是质数
        for(ll j = i*i;j<=N;j+=i){ // 筛数
            if(base[j] == 1)base[j] = i;
        }
    }
    rep(i,2,N+1){
        ll b = base[i]; // 找一个数的质因子
        int cnt = 0; // 该质因子幂次
        int ii = i; // 去掉这个质因子以外剩余部分
        while(ii % b == 0){ 
            cnt ++;
            ii/=b;
        }
        sum[i] = sum[ii] * (mypow(b,cnt+1)-1)/(b-1); // 所有质因子的和, 等比数列求和公式
        ans[i] = ans[i-1] + (sum[i] == i*2); // 是否满足题意，预处理答案
    }
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",ans[n]); // 直接输出
    }
    return 0;
}

复杂度分析

设询问次数为$mm$

时间复杂度: 质数表处理$O(n)O(n)$, 对每个数，计算它的因数和，最大质因子个数为log级别，所以$O(n\cdot log(n))O(n\backslash cdot\; log(n))$, 计算答案，基于上面的结果$O(1)O(1)$,每次询问$O(1)O(1)$的查询代价，所以总时间复杂度为$O(n\cdot log(n)+m)O(n\backslash cdot\; log(n)+m)$

空间复杂度: 空间主要耗在上面的三个vector，所以空间复杂度为$O(n)O(n)$

枚举

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

ll getsum(ll v){ 
    ll cnt = 0;
    rep(i,1,v+1){ // 枚举
        cnt += (v%i==0?i:0);
    }
    return cnt;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        int ans = 0; // 答案
        rep(i,2,n+1){
            ans += getsum(i) == i*2; // 是否满足题意，预处理答案
        }
        printf("%d\n",ans); // 直接输出
    }
    return 0;
}

复杂度分析

时间复杂度: 对于每个查询，枚举到n，所以时间复杂度为$O(mn)O(mn)$, 应该超时的，而数据太弱，竟然它过了

空间复杂度: 常数大小的额外空间消耗，所以空间复杂度为$O(1)O(1)$