欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[P5172] Sum

程序员文章站 2023-04-01 08:06:44
のすたの“类欧几里得算法”第一题 sum 【题意】 给入$n,r$,求$\sum_{d=1}^n( 1)^{\lfloor d\sqrt r \rfloor}$。 【分析】 只需要考虑所有$d$中,$\lfloor d\sqrt r\rfloor$为偶数的个数。显然$\lfloor x\rfloor ......

のすたの“类欧几里得算法”第一题 sum

【题意】

给入\(n,r\),求\(\sum_{d=1}^n(-1)^{\lfloor d\sqrt r \rfloor}\)

【分析】

只需要考虑所有\(d\)中,\(\lfloor d\sqrt r\rfloor\)为偶数的个数。显然\(\lfloor x\rfloor\)为偶数\(\leftrightarrow \lfloor x\rfloor=2\times\lfloor\frac{x}{2}\rfloor\)。 那么原式可以改写为:
\[ \sum_{d=1}^n 1-2\times(\lfloor d\sqrt r\rfloor\bmod 2)=\sum_{d=1}^n 1-2\times(\lfloor d\sqrt r\rfloor-2\times\lfloor\frac{d\sqrt r}{2}\rfloor)\\ =n-2\times\sum_{d=1}^n\lfloor d\sqrt r\rfloor+4\times\sum_{d=1}^n\lfloor\frac{d\sqrt r}{2}\rfloor \]
不妨设\(f(a,b,c,n)=\sum_{d=1}^n\lfloor d\times\frac{a\sqrt r+b}{c}\rfloor\),那么原式即为
\[ n-2\times f(1,0,1,n)+4\times f(1,0,2,n) \]
考虑关于\(f(a,b,c,n)\)的算法,(开始扣题了),设\(k=\frac{a\sqrt r +b}{c}\)

\(k\ge1\)时,\(k\)可以拆为一个正数+小于1的非负实数,即
\[ f(a,b,c,n)=\sum_{d=1}^n \lfloor d\times k\rfloor=\sum_{d=1}^n d\times\lfloor k\rfloor+\lfloor d\times(k-\lfloor k\rfloor)\rfloor\\ =\frac{n(n+1)}{2}\lfloor k\rfloor+\sum_{d=1}^n\lfloor d\times\frac{a\sqrt r+b-\lfloor k\rfloor\times c}{c}\rfloor\\ =\frac{n(n+1)}{2}\lfloor k\rfloor+f(a,b-\lfloor k\rfloor\times c,c,n) \]
\(k<1\)时,(比如上面递归的那层),可以看作是满足
\[ \begin{cases} 0<x\le n\\ 0<y\le x\times k\\ x\in z\\ y\in z \end{cases} \]
的点数。考虑再矩形\((1,1)(n,\lfloor n\times k\rfloor)\)内容斥可得个数为\(n\times\lfloor n\times k\rfloor\) 减去左上三角的部分,而那部分可当作是\(y=x\times k,\ x\in[1,n]\)的反函数\(y=x\times \dfrac{1}{k}, x\in[1,\lfloor n\times k\rfloor]\)

其中\(\dfrac{1}{k}=\dfrac{c}{a\sqrt r+b}=\dfrac{c(a\sqrt r-b)}{(a\sqrt r+b)(a\sqrt r-b)}=\dfrac{ac\sqrt r-bc}{a^2r-b^2}\)
\[ f(a,b,c,n)=n\times\lfloor n\times k\rfloor-f(ac,-bc,a^2r-b^2,\lfloor n\times k\rfloor) \]
可以发现,情况一二交替递归,且每轮的总的变化与欧几里得算法相似,故知其复杂度为\(\log​\)级的。

难度海星。。

然而当\(r\)为完全平方数时需要单独算,大概会爆ll吧。。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,r;
double x;
ll f(ll a,ll b,ll c,ll n) {
    if(!n) return 0;
    ll d=__gcd(__gcd(a,b),c);
    a/=d, b/=d, c/=d;
    double k=(a*x+b)/c;
    if(k>=1) return n*(n+1)/2*(ll)(k)+f(a,b-(ll)(k)*c,c,n);
    else return n*(ll)(n*k)-f(a*c,-b*c,a*a*r-b*b,(ll)(n*k));
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld",&n,&r);
        x=sqrt(r);
        ll c=x;
        if(c*c==r) {
            if(c&1) printf("%lld\n",n-2*((n+1)/2));
            else printf("%lld\n",n);
        } 
        else printf("%lld\n",n-2*f(1,0,1,n)+4*f(1,0,2,n));
    }
    return 0;
}