BZOJ 3817 - Sum

#数学 #类欧几里得
Published on 2017-03-31

题目地址

描述

给定正整数 n,r(n≤109,r≤104)n, r(n\le {10}^9, r \le {10}^4)，求

∑d=1n(−1)⌊d×r×d⌋ \sum_{d = 1}^{n}{(-1)^{\left\lfloor \sqrt{d \times r\times d} \right\rfloor}}

你需要回答 T(T≤104)T(T\le {10}^4) 组询问。

分析

前面的部分直接 O(1)O(1) 计算，现在我们考虑后面的部分，我们的目的是将其转化为与最初的和式类似的形式

∑i=1n⌊(ar+bc−⌊ar+bc⌋)⋅i⌋ \sum_{i = 1}^n\left\lfloor\left(\frac {a\sqrt r + b} c - \left\lfloor\frac {a\sqrt r + b} c\right\rfloor\right)\cdot i\right\rfloor

通分

∑i=1n⌊ar+b−c⋅⌊ar+bc⌋c⋅i⌋ \sum_{i = 1}^n\left\lfloor\frac {a\sqrt r + b - c\cdot \left\lfloor\frac {a\sqrt r + b} c\right\rfloor} c\cdot i\right\rfloor

设

t=b−c⋅⌊ar+bc⌋ t = b - c\cdot \left\lfloor\frac {a\sqrt r + b} c\right\rfloor

式子化为

∑i=1n⌊ar+tc⋅i⌋ \sum_{i = 1}^n\left\lfloor\frac {a\sqrt r + t} c\cdot i\right\rfloor

根据类欧几里得的套路，展开为两个和式，并交换求和顺序

观察不等式，我们将其转化为对 ii 的限制，并分母有理化

设 M=⌊ar+tc⋅n⌋M = \left\lfloor\frac {a\sqrt r + t}c\cdot n\right\rfloor，现在第二个和式可以直接去掉了

中间的和式，稍微统计一下就好了，后面的和式可以递归。于是现在 nn 变成了 ⌊ar+tc⋅n⌋\left\lfloor\frac {a\sqrt r + t}c\cdot n\right\rfloor，由于 ar+tc\frac {a\sqrt r + t}c 是 ar+bc\frac {a\sqrt r + b} c 的小数部分，所以必然 <1< 1，所以 nn 每次乘一个小于 11 的数并下取整，这就说明 nn 变到 11 只需经过 O(logn)O(\log n) 次递归，由于每次需要对 a,b,ca, b, c 进行约分，所以这个算法是 O(log2n)O(\log^2 n) 的。

代码

//  Created by Sengxian on 2017/03/21.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 3817 类欧几里得
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

inline ll force(ll n, ll a, ll b, ll c, ll r) {
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += floor(i * (a * (long double)sqrt(r) + b) / c);
    }
    return ans;
}

ll solve(ll n, ll a, ll b, ll c, ll r) {
    if (n <= 0) return 0;
    ll g = gcd(a, gcd(b, c));
    a /= g, b /= g, c /= g;
    long double sqrtR = sqrt(r);
    ll x = (a * sqrtR + b) / c;
    ll t = b - c * x;
    ll M = n * (a * sqrtR + t) / c;
    long double t1 = a * c * sqrtR - t * c;
    ll t2 = a * a * r - t * t;
    ll ans = n * (n + 1) / 2 * x + M * n - solve(M, a * c, -t * c, t2, r);;
    if (floor(t1) == t1) {
        ll l = t2 / gcd(t2, (ll)t1);
        if (l != 0) ans += M / l;
    }
    return ans;
}

int main() {
    int caseNum = readInt();
    while (caseNum--) {
        int n = readInt(), r = readInt();
        ll cnt = solve(n, 1, 0, 1, r) - solve(n, 1, 0, 2, r) * 2;
        printf("%lld\n", n - 2 * cnt);
    }
    return 0;
}
BZOJ 3995 - [SDOI2015]道路修建