SP15864 题解 & 迷思

NaCly_Fish · 2023-04-30 18:16:06 · 题解

题目链接

题目要求我们求出前 x 个 3-smooth 数之和，其通项似乎是没有封闭形式的，但是它有一个不错的估计：

设 b_n 为 a_n 的估计值，我们可以尝试统计不超过 b_n 的 a_i 有多少个（这是很容易 \Theta(\sqrt n) 处理的）。可以发现在数据范围之内，它与 n 的绝对误差很小，似乎没有超过 5 的。

那就有一种比较靠谱的做法：先统计不超过 b_n 的 a_i 之和，同时在计算过程中保留大于 b_n 的、最小的几个数；和不超过 b_n 的、最大的几个数。这样就可以在最后调整误差。

由此可以得到代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
#define N 100003
#define double long double
using namespace std;

int p;

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

struct node{
    int v;
    double lv;
    inline node(int _v=0,double _lv=0):v(_v),lv(_lv){}
    inline bool operator < (const node& rhs) const{
        return lv < rhs.lv;
    }
    inline bool operator > (const node& rhs) const{
        return lv > rhs.lv;
    }
};

const double ln3 = log(3),ln2 = log(2);
ll n,cnt;
int L,d,ans,pw3 = 1,tmp;
priority_queue<node> ql;
priority_queue<node,vector<node>,greater<node> > qs;
vector<int> qL,qS;

int main(){
    scanf("%lld%d",&n,&p);
    double x = sqrt(2*ln2*ln3)*sqrt(n)-log(sqrt(6)),y;
    L = x/ln3;
    for(int j=0;j<=L;++j){
        d = (x-j*ln3)/ln2;
        tmp = (ll)power(2,d)*pw3%p;
        y = d*ln2+j*ln3;
        qs.push(node(tmp,y)),ql.push(node(2*tmp%p,y+ln2));
        ans = (ans+2*tmp-pw3)%p,cnt += d+1;
        if(ql.size()>9) ql.pop(),qs.pop();
        pw3 = 3*pw3%p;
    }
    while(!ql.empty()) qL.push_back(ql.top().v),ql.pop();
    while(!qs.empty()) qS.push_back(qs.top().v),qs.pop();
    while(cnt<n){
        ans = (ans+qL[qL.size()-1])%p;
        cnt++,qL.pop_back();
    }
    while(cnt>n){
        ans = (ans-qS[qS.size()-1])%p;
        cnt--,qS.pop_back();
    }
    printf("%d",(ans+p)%p);
    return 0;   
}

update：这个估计值实际上很好算，就是先用估计 不超过 n 的 a_i 有多少个，设为 f(n)。那只需要求出 f(n) 的反函数，就是 a_n 的估计值了。至于 f(n) 怎么表示，有一个简单的做法是积分，不过大概还可以进一步估计，等有时间了再来补一下。