一个筛子

一个筛子

做法：

  • 求：\(\displaystyle \sum_{i=2}^{n} f(i)\),\(i\in prime\)

  • 初始时：S[x]=\(\displaystyle \sum_{i=2}^{x} f(i)\)

  • for prime：primelist

    • for x in range[n,sqrt(p)]
      • S[x]-=(S[x/p]-S[p-1])*\(f(x)\)

代码(HDU 6889)：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair pii;
#define mp make_pair
#define fi first
#define se second
#define All(x) (x).begin(), (x).end()
#define Y1 "YES"
#define N1 "NO"
#define ENDL '\n'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
inline ll read() {  // not solve LLONG_MIN LMAX=9,223,372,036,854,775,807
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
typedef __uint128_t returnT;
typedef unsigned long long argT;
typedef unsigned int sqargT;
constexpr argT maxm=1e5+1;
sqargT primelist[maxm],pcnt=0;
bool isnprime[maxm];
double inv[maxm];
inline void init(){
    constexpr argT m=maxm-1;
//    constexpr argT mz=m/log10(m);
    primelist[++pcnt]=2;
    for(argT i = 1;i <= m; ++i)
        inv[i] = 1.0 / i;
    // i*i may overflow
    for(argT j = 4; j <=m; j+=2)
    isnprime[j] = true;
    for (argT i = 3; i <= m; i+=2){
        if(!isnprime[i]){
            primelist[++pcnt]=i;
            // i*i may overflow
            for(argT j = i * i; j <=m; j+=i)
            isnprime[j] = true;
        }
    }
    return ;
}
argT a[maxm];
argT b[maxm];
//int ppt=0;
inline argT n34divlognsieve(const argT n) {
    if (n <= 1) return 0;
    const sqargT m = sqrt(n);
    constexpr double eps = 1e-7;
    for (sqargT i = 2; i <= m; ++i)    
        a[i] = a[i - 1] + i;
    for (sqargT i = 1; i <= m; ++i) {  
        returnT sum_n = n / i;
        b[i] = (sum_n + sum_n * sum_n) / 2 - 1;
    }
    const sqargT pt=upper_bound(primelist+1,primelist+1+pcnt,m)-primelist;
    for (sqargT r=1;r= limpp; --i)
            a[i] -= (a[(unsigned int)(i * invprime + eps)] - t) * prime; 
    }
    return b[1];
}
int main() {
    init();
    int t=read();
    while(t--){
        argT n=read();
        int k=read();
        returnT ans = (returnT)n*(3+n)/2+n34divlognsieve(n+1)-4 ;
        printf("%d\n",(int)(ans%k));
    }
    return 0;
}

耗时

使用i7-10710U，输入的n为1e10时，ans函数执行平均需要约83ms，稍作优化即可达到48ms,HDU 6889实测514MS!

代码(HDU 5901)

#include
#include
#include
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uint;
constexpr uint maxm=sqrt(1e11)+1;//maxn=1e12
uint primelist[maxm],pcnt=0;
bool isnprime[maxm];
double inv[maxm];
inline void init(){
    constexpr uint m=maxm-1;
    primelist[++pcnt]=2;
    for(uint i=1;i<=m;++i)inv[i]=1.0/i;
    for(uint j=4;j<=m;j+=2)isnprime[j]=true;
    for(uint i=3;i<=m;i+=2){
        if(!isnprime[i]){
            primelist[++pcnt]=i;
            // i*i may overflow
            for(ull j=(ull)i*i;j<=m;j+=i)
            isnprime[j]=true;
        }
    }
    return ;
}
uint a[maxm];
ull b[maxm];
inline ull n34divlognsieve(const ull n) {
    if (n<=1) return 0;
    const uint m=sqrt(n);
    constexpr double eps=1e-7;
    for(uint i=2;i<=m;++i)a[i]=a[i-1]+1;//sum
    for(uint i=1;i<=m;++i)b[i]=n/i-1;//sum
    const uint pt=upper_bound(primelist+1,primelist+1+pcnt,m)-primelist;
    for(uint r=1;r=prime*prime;--i)
            a[i]-=(a[(uint)(i*inv[prime]+eps)]-a[prime-1]); 
    }
    return b[1];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    ull n;
    while(cin>>n){
        cout<
算法模板

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

题解 Count on a tree II/【模板】树分块

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

标签