2016 UESTC Training for Math F – 粗心的谭爷 素数线性筛法的推广

Source

2016 UESTC Training for Math

My Solution

素数线性筛法的推广

对于每个数分解质因数算答案，复杂度O(NlogN)，

明显会TLE

需要O(N)的算法

回顾一下线性筛法

每个数字都被它的最小素因子筛，可递推

对于每个数字，维护3个值

·最终的答案 ans[i]

·最后被筛的素因子（即最小素因子） pre[i]

·被最小素因子筛了几次（即当前最小素因子的次数）  times[i]

在记录的过程中进行素数筛选，而没有先套个素数线性筛选的版，然后在算ans， sum

若i%prime[j]==0，说明i已经有素因子prime[j]了，转移时最小素因子的次数++即可

若i%prime[j]!=0，则将当前的最小素因子-次数统计到答案，并更新新的最小素因子，令次数为1

最后求和得到答案

此外对于calc()函数，

inline LL calc(LL p, LL t)

{

if(t == 1) return p;      //!前面漏了这里了，如果指数times[i]是 1 则return p

LL s = 0;

int cntt = 0, de = 1;

while(t / de > 0){

cntt++;

de *= 10;

}

//cout<<p*pow(10, cntt)<<" "<<t<<endl;

s = p*de + t;

return s;

}

也使自己意识到了pow(10, cntt)的浮点误差造成奇怪偏差， 比如用pow是那两个分开输出200 30

但相加输出变成了229， 神奇的少了1.

还是多用快速幂好了，尽管这里这些都不需要。p*de就好了。

复杂度 O(n)

#include 
#include 
#include 
//#include 
using namespace std;
typedef long long LL;
const int maxn = 1e7 + 9;
LL p[maxn], pre[maxn], times[maxn], ans[maxn];
bool is_notprime[maxn];
/*
bool valid[maxn];

void getPrime(int n)
{
    int tot = 0;
    memset(valid, true, sizeof valid);
    for(int i = 2; i <= n; i++){
        if(valid[i]){
            tot++;
            p[tot] = i;
        }
        for(int j = 1; ((j <= tot) && (i * p[j] <= n)); j++){ valid[i * p[j]] = false; if(i % p[j] == 0) break; } } } */ inline LL calc(LL p, LL t) { if(t == 1) return p; //!前面漏了这里了，如果指数times[i]是 1 则return p LL s = 0; int cntt = 0, de = 1; while(t / de > 0){
        cntt++;
        de *= 10;
    }
    //cout<<p*pow(10, cntt)<<" "<<t<<endl;
    s = p*de + t;
    return s;
}


int main()
{
    int n, cnt = 0;
    //cout<<calc(2, 1)<<" "<<calc(3,1)<<endl;

    scanf("%d", &n);
    LL sum = 1;
    memset(is_notprime, false, sizeof is_notprime);


    for(int i = 2; i <= n; i++){
        if(!is_notprime[i]){
            p[cnt++] = i, ans[i] = 1, pre[i] = i, times[i] = 1;
        }
        for(int j = 0; j < cnt && i*p[j] <= n; j++){
            is_notprime[i * p[j]] = true;
            pre[i * p[j]] = p[j];
            if(i % p[j] != 0){
                ans[i * p[j]] = ans[i]*calc(pre[i], times[i]);
                times[i * p[j]] = 1;
            }
            else{
                ans[i * p[j]] = ans[i];
                times[i * p[j]] = times[i] + 1;
                break;
            }
        }
        sum += ans[i] * calc(pre[i], times[i]);
    }
    printf("%lld", sum);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx