「学习笔记」类欧几里得算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了「学习笔记」类欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3385字，纯文字阅读大概需要5分钟。

内容图文

「学习笔记」类欧几里得算法

现有多组询问，要求在 \(O(\log n)\) 求三个有趣式子的和。

设

\[f(a,b,c,n)=\sum_{i=0}^{n}\lfloor \frac {ai+b}{c}\rfloor\]

\[g(a,b,c,n)=\sum_{i=0}^{n}\lfloor \frac {ai+b}{c}\rfloor^2\]

\[h(a,b,c,n)=\sum_{i=0}^{n}i\lfloor \frac {ai+b}{c}\rfloor\]

\(t_1=\lfloor \frac ac\rfloor,t_2=\lfloor \frac bc\rfloor\)

\(S_1(n)=\sum_{i=0}^{n}i,S_2(n)=\sum_{i=0}^{n}i^2\)

\(m=\lfloor \frac {an+b}{c}\rfloor\)

求 \(f(a,b,c,n)\)

若 \(a\geq c\) 或 \(b\geq c\)

\(\lfloor \frac {ai+b}{c}\rfloor=\lfloor \frac {(a\ \text{mod}\ c)i+(b\ \text{mod}\ c)}{c}\rfloor+t_1i+t_2\)

\(\Longrightarrow f(a,b,c,n)=f(a\ \text{mod}\ c,b\ \text{mod}\ c,c,n)+t_1S_1(n)+(n+1)t_2\)

若 \(a<c\) 且 \(b<c\)

\[f(a,b,c,n)=\sum_{i=0}^{n}\sum_{j=1}^{m}[\lfloor \frac {ai+b}{c}\rfloor\geq j]=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[\lfloor \frac {ai+b}{c}\rfloor\geq j+1]\]

\[=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[ai+b\geq cj+c]=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[ai\geq cj+c-b]=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[ai> cj+c-b-1]\]

\[\sum_{i=0}^{n}\sum_{j=0}^{m-1}[i>\lfloor \frac {cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>\lfloor \frac {cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m-1}n-\lfloor \frac {cj+c-b-1}{a}\rfloor\]

\[=mn-f(c,c-b-1,a,m-1)\]

求 \(g(a,b,c,n)\) 和 \(h(a,b,c,n)\)

由于式子过长且与 \(f(a,b,c,n)\) 的推导过程类似，所以只有简化过程。

若 \(a\geq c\) 或 \(b\geq c\)

\(g(a,b,c,n)=g(a\ \text{mod}\ c,b\ \text{mod}\ c,c,n)+2t_1h(a\ \text{mod}\ c,b\ \text{mod}\ c,c,n)+2t_2f(a\ \text{mod}\ c,b\ \text{mod}\ c,c,n)\)

\(+t_1^2S_2(n)+2t_1t_2S_1(n)+(n+1)t_2^2\)

\(h(a,b,c,n)=h(a\ \text{mod}\ c,b\ \text{mod}\ c,c,n)+t_1S_2(n)+t_2S_1(n)\)

若 \(a<c\) 且 \(b<c\)

\[g(a,b,c,n)=\sum_{j=0}^{m-1}\sum_{k=0}^{m-1}n-\max(\lfloor \frac {cj+c-b-1}{a}\rfloor,\lfloor \frac {ck+c-b-1}{a}\rfloor)\]

\[=m^2n-2\sum_{j=0}^{m-1}(j+1)\lfloor \frac {cj+c-b-1}{a}\rfloor+\sum_{j=0}^{m-1}\lfloor \frac {cj+c-b-1}{a}\rfloor\]

\[=m^2n-2h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\]

\[h(a,b,c,n)=\sum_{j=0}^{m-1}\sum_{i=0}^{n}i[i>\lfloor \frac {cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m-1}S_1(n)-S_1(\lfloor \frac {cj+c-b-1}{a}\rfloor)\]

\[=mS_1(n)-\frac {g(c,c-b-1,a,m-1)}{2}-\frac {f(c,c-b-1,a,m-1)}{2}\]

边界条件

若 \(n=0\)

\[f(a,b,c,n)=t_2,g(a,b,c,n)=t_2^2,h(a,b,c,n)=0\]

若 \(a=0\)

\[f(a,b,c,n)=(n+1)t_2,g(a,b,c,n)=(n+1)t_2^2,h(a,b,c,n)=t_2S_1(n)\]

\(Code\ Below:\)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const ll inv2=499122177;
const ll inv6=166374059;
ll n,a,b,c;

struct node{
    ll f,g,h;
};

inline ll S1(ll n){
    return n*(n+1)%mod*inv2%mod;
}

inline ll S2(ll n){
    return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}

inline node solve(ll a,ll b,ll c,ll n){
    ll t1=a/c,t2=b/c,s1=S1(n),s2=S2(n),m=(a*n+b)/c;
    node ans,now;ans.f=ans.g=ans.h=0;
    if(!n){
        ans.f=t2;
        ans.g=t2*t2%mod;
        return ans;
    }
    if(!a){
        ans.f=(n+1)*t2%mod;
        ans.g=(n+1)*t2%mod*t2%mod;
        ans.h=t2*s1%mod;
        return ans;
    }
    if(a>=c||b>=c){
        now=solve(a%c,b%c,c,n);
        ans.f=(now.f+t1*s1+(n+1)*t2)%mod;
        ans.g=(now.g+2*t1*now.h+2*t2*now.f+t1*t1%mod*s2+2*t1*t2%mod*s1+(n+1)*t2%mod*t2)%mod;
        ans.h=(now.h+t1*s2+t2*s1)%mod;
        return ans;
    }
    now=solve(c,c-b-1,a,m-1);
    ans.f=(m*n-now.f)%mod;ans.f=(ans.f+mod)%mod;
    ans.g=(m*m%mod*n-2*now.h-now.f);ans.g=(ans.g+mod)%mod;
    ans.h=(m*s1-now.g*inv2-now.f*inv2)%mod;ans.h=(ans.h+mod)%mod;
    return ans;
}

int main()
{
    ll T;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
        node ans=solve(a,b,c,n);
        printf("%lld %lld %lld\n",ans.f,ans.g,ans.h);       
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的「学习笔记」类欧几里得算法全部内容，希望文章能够帮你解决「学习笔记」类欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---