题解：P5172 Sum

yanzihe · 2024-12-23 07:48:39 · 题解

来一篇最没有思维难度的题解。

初步思路

考虑题目要我们求 n 个数中奇数的个数，于是我们考虑如何区分奇数和偶数。

发现对于奇数 p，2\times \lfloor\frac{p}{2}\rfloor=p-1。
对于偶数 q，2\times \lfloor\frac{q}{2}\rfloor=q。
这启发我们利用 \sum_{i=1}^{n}(2\times \lfloor\frac{a_i}{2}\rfloor) 和 \sum_{i=1}^{n}a_i 之间的差来判断数列 \{a_i\} 中奇数个数，具体来说，\{a_i\} 中奇数个数 = \sum_{i=1}^{n}a_i-2\times\sum_{i=1}^{n}\lfloor\frac{a_i}{2}\rfloor。

现在考虑如何求 \sum_{i=1}^{n}\lfloor i\sqrt r\rfloor。
考虑类欧可以让我们求出 \sum_{i=1}^{n}\lfloor i\times\frac{a}{b}\rfloor，所以只需要找到一个接近 \sqrt r 的 \frac{a}{b} 即可。
（\sum_{i=1}^{n}\lfloor\frac{i\sqrt r}{2}\rfloor 的求法类似）

寻找逼近 \sqrt r 的有理数

有一个初步的想法：

b\leftarrow 10^{30}

a\leftarrow \lfloor\sqrt r\times b\rfloor

这样得到的 \frac{a}{b} 是一个比较好的近似。（必须使用 __int128_t 存储）使用这个方法可以得到 40 分的高分。

考虑这个方法不够精确的原因在哪里，其实在于 sqrt 这个函数本身就无法精确到小数点后 30 位。于是为了提高精度，我们必须使用保证精确的整数运算来代替浮点数运算。

考虑固定分母 b 之后，对分子二分：

__int128_t b=1e15;
__int128_t l=0, r=b*100, a=0;
while(l<=r){
    __int128_t mid=(l+r)/2;
    //这里的ri就是原题中的r
    if(mid*mid<=(__int128_t)ri*b*b){//mid<=sqrt(ri)*b两边开平方，得到mid^2<=ri*b^2
        a=mid;
        l=mid+1;
    }else{
        r=mid-1;
    }
}

这样可以得到 50 分的高分，考虑精度不够的原因是分母只有 10^{15}，但如果进一步开大分母，在乘法运算时就会超过 __int128_t。

那么就只能开大分母，并写高精度乘法了：

typedef long long ll;
vector <ll> multiply(vector <ll> a, vector <ll> b){//高精度乘法
    vector <ll> res;res.resize(a.size()+b.size()+2);
    rep(i, 0, a.size()-1)rep(j, 0, b.size()-1)res[i+j]+=a[i]*b[j];
    rep(i, 0, res.size()-1){
        if(res[i]>=10){res[i+1]+=res[i]/10;res[i]%=10;}
    }
    return res;
}
vector <ll> into(__int128_t a){//把a转成高精度形式
    vector <ll> res;
    while(a){
        res.push_back(a%10);
        a/=10;
    }
    return res;
}
bool Greater(vector <ll> a, vector <ll> b){//比较两个高精度形式的数
    while(a.back()==0)a.pop_back();
    while(b.back()==0)b.pop_back();
    if(a.size()!=b.size())return a.size()>b.size();
    rrep(i, a.size()-1, 0)if(a[i]!=b[i])return a[i]>b[i];
    return false;
}

因为复杂度是 O(T(\log n)^3) 于是得到了 60 分的好成绩。
此时有 2 个方法：

使用 FFT/NTT 代替暴力乘法，复杂度 O(T(\log n)^2\log \log n) 得分未知。
优化常数，原先使用 vector 存储十进制下的整数，但是一个 long long 只存一个 [0, 9] 之间的整数太过浪费，于是用 vector 存储十亿进制下的整数，复杂度不变，但是常数得到很大的优化。

AC代码


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=a;i<=b;i++)
#define rrep(i, a, b) for(ll i=a;i>=b;i--)
__int128_t f(__int128_t n, __int128_t a, __int128_t b, __int128_t c){
    __int128_t ans=n*(n+1)/2*((ll)(a/c))+(n+1)*((ll)(b/c));
    a%=c;b%=c;
    if(a==0)return ans;
    __int128_t m=(a*n+b)/c;
    ans+=n*m-f(m-1, c, c-b-1, a);
    return ans;
}
ll t, n, ri;
#define B 1000000000//B是进制
vector <ll> multiply(vector <ll> a, vector <ll> b){//高精度乘法
    vector <ll> res;res.resize(a.size()+b.size()+2);
    rep(i, 0, a.size()-1)rep(j, 0, b.size()-1)res[i+j]+=a[i]*b[j];
    rep(i, 0, res.size()-1){
        if(res[i]>=B){res[i+1]+=res[i]/B;res[i]%=B;}
    }
    return res;
}
vector <ll> into(__int128_t a){//把a转成十亿进制的高精度形式（每一位存储0～999999999的数）
    vector <ll> res;
    while(a){
        res.push_back(a%B);
        a/=B;
    }
    return res;
}
bool Greater(vector <ll> a, vector <ll> b){//比较两个高精度形式的数
    while(a.back()==0)a.pop_back();
    while(b.back()==0)b.pop_back();
    if(a.size()!=b.size())return a.size()>b.size();
    rrep(i, a.size()-1, 0)if(a[i]!=b[i])return a[i]>b[i];
    return false;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> ri;
        __int128_t b=1e25;
        __int128_t l=0, r=b*100, a=0;
        vector <ll> rbb=multiply(multiply(into(ri), into(b)), into(b));//把ri*b*b预计算出来
        while(l<=r){//二分
            __int128_t mid=(l+r)/2;
            if(!Greater(multiply(into(mid),into(mid)),rbb)){
                a=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        __int128_t cnt1=f(n, a, 0, b)-f(n, a, 0, b*2)*2;//类欧几里得算法
        cout << (ll)((n-cnt1)-cnt1) << endl;
    }
    return 0;
}