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;
}