会 F 写不来 E 了属于是……

题意

给定 \(a,b,c,d,n\) ，令 \(f(x)=a+\lfloor\frac{x}{b}\rfloor,f(x)=c+\lfloor\frac{x}{d}\rfloor\) ，求 \(\sum_{i=1}^n[f(x)=g(x)]\) 。

\(T\) 组询问。 \((1\le T\le2\times10^5,1\le a,b,c,d,n\le10^6)\)

题解

数论大讨论水平仍然不行！！！

首先不考虑下取整这个条件，那么答案只会在 \(|f(x)-g(x)|\le1\) 中。

先找到这个区间的两个端点，并将这个区间于 \(f(x)=g(x)\) 处断开，对两边分别讨论，此处不写一些关于区间开闭的细节了。

现在重新考虑要下取整的 \(f\) 和 \(g\) 了，不妨设在此段区间内 \(f(x)\ge g(x)\) 。

其实 \(\sum_{i=l}^r a+\lfloor\frac{x}{b}\rfloor\) 和 \(\sum_{i=l}^r c+\lfloor\frac{x}{d}\rfloor\) 是容易算出来的，考虑这两个东西的差。

显然，这两者的差为多少，那么 \(f(x)>g(x)\) 的地方就有多少，又因为 \(f(x)-g(x)\le1\) ，所以容易算出 \(f(x)=g(x)\) 的 \(x\) 个数。

单次询问 \(O(1)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum(ll a,ll b) {ll n=a/b;return n*(n-1)/2*b+(a-b*n)*n;}
ll calc(ll l,ll r,ll a,ll b) {return a*(r-l)+sum(r,b)-sum(l,b);}
ll solve(){
	ll n,a,b,c,d,l,r,ans=0;
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	if(b==d) return a==c?n:0;
	if(b>d) swap(a,c),swap(b,d);
	l=max(0ll,b*d*(c-a-1)/(d-b))+1;
	r=min(n,b*d*(c-a)/(d-b))+1;
	if(l<r) ans=r-l-calc(l,r,c,d)+calc(l,r,a,b);
	l=max(0ll,b*d*(c-a)/(d-b))+1;
	r=min(n,b*d*(c-a+1)/(d-b))+1;
	if(l<r) ans+=r-l-calc(l,r,a,b)+calc(l,r,c,d);
	return ans;
}
signed main(){
	int t;scanf("%d",&t);
	while(t--) printf("%lld\n",solve());
	return 0;
}