526互联

C1. Good Subarrays (Easy Version)（推公式找性质）

发布时间 2023-12-05 11:00:30作者: cxy8

思路：

\[能想到平方是比较特殊的，因为x*x一定是x的倍数也就是说\sqrt[2]{x*x} = {x} \]

\[所以需要考虑平法之间的数手模一下样例可以发现 [x^2 ,(x+1)^2)之间是x倍数的有x^2 \]

\[x*(x+1), x*(x+2)这三个，所以可以知道平方之间有三个，只要讨论一下出来整个区间边界还有多少个 \]

这里可以用一个前缀和去优化就只用考虑右边界，右边界和上面三个讨论

\[[x^2 ,(x+1) * x) \quad 答案+1 \]

\[[(x+1) * x ,(x+2) * x) \quad 答案+1 \]

\[[(x+2) * x ,(x+1)^2) \quad 答案+1 \]

#include <bits/stdc++.h> 
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<t<<endl;

using namespace std;
const int N = 1e6 + 10;
int t;

ll get(ll x)
{
	ll res = 0, m = sqrt(x);
	res += (m - 1) * 3;
	if(x >= m * m) res ++;
	if(x >= (m + 1) * m)	res ++;
	if(x >= (m + 2) * m)	res ++;
	return res;
}

void solve()
{
	ll l, r, ans = 0; cin >> l >> r;
	
	cout << get(r) - get(l - 1) << endl;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	freopen("1.in", "r", stdin);
	cin >> t;
//	while(t --)	
//	solve();
	debug(t) 
	return 0;
}