Math Problem（数论+二分+前缀和）

Math Problem

题目描述

已知整数 a, a^3 除 192 的余数是 1 。求区间 [L,R] 之间满足条件的 a 的累加和是多少？

输入

第一行是一个整数 T(1≤T≤10000)，表示样例的个数。
每个样例包含两个整数 L,R, 1≤L≤R≤10^9。

输出

输出描述
每行输出一个样例的结果。

样例输入

1
1 10

样例输出

1

思路

本题来自某大学acm训练的题，由于我太菜只会暴力，然后我去

请教了大佬，结果是数论+二分+前缀和。。首先是数学证明(a^3-1)%192==0,即 (a-1)(a^2+ a+1)%192 == 0, 即对于所有的(a-1)% 192 == 0,
(a^3-1)%192==0,恒成立，所以我们枚举192的倍数+1，前缀和处理这些数的和，然后二分左右端点，由sum[r]-sum[l-1]即可

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
int t;
ll sum[5300000];

ll du(ll x) {
    if (x <= 0) return 0;
    else return sum[x] - sum[x - 1];
}

ll f1(ll a, ll l, ll r) {
    ll mid = (l + r) / 2;
    ll rz = du(mid - 1);
    ll r1 = du(mid);
    ll rr = du(mid + 1);
    if (rz < a && r1 > a) return mid;
    if (r1 < a && rr > a) return mid + 1;
    if (a == r1) return mid;
    if (a > r1) return f1(a, mid + 1, r);
    if (a < r1) return f1(a, l, mid - 1);
}

ll f2(ll a, ll l, ll r) {
    ll mid = (l + r) / 2;
    ll rz = du(mid - 1);
    ll r1 = du(mid);
    ll rr = du(mid + 1);
    if (rz < a && r1 > a) return mid - 1;
    if (r1 < a && rr > a) return mid;
    if (a == r1) return mid;
    if (a > r1) return f2(a, mid + 1, r);
    if (a < r1) return f2(a, l, mid - 1);
}


int main() {
    ll c = 1;
    for (ll i = 0; i <= 1000000000; i += 192) {
        ll a = i + 1;
        sum[c] = sum[c - 1] + a;
        c++;
    }
    cin >> t;
    while (t--) {
        ll l, r;
        cin >> l >> r;
        ll zl = f1(l, 1, c);
        ll zr = f2(r, 1, c);
        if (zl == 0)
            cout << sum[zr] << endl;
        else
            cout << sum[zr] - sum[zl - 1] << endl;
    }
    return 0;
}