C++(clang++11) 解法, 执行用时: 266ms, 内存消耗: 2288K, 提交时间: 2021-05-14 20:13:25

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y) {
	if(!b) { x=1,y=0; return a; }
	int d=exgcd(b,a%b,y,x); y-=a/b*x;
	return d;
}
pair<int,int> work(int x,int y,int z) {
	int a,b; int d=exgcd(x,z,a,b);
	if(y%d!=0) return make_pair(-1,-1);
	int T=z/d; a=(a*(y/d)%T+T)%T;
	return make_pair(a,T);
}
int x,y,z,a,l,r;
int calc(int n,pair<int,int> s1,pair<int,int> s2) {
	int ans=n+1;
	if(s1.first>=0) ans-=(n-s1.first+s1.second)/s1.second;
	if(s2.first>=0) ans-=(n-s2.first+s2.second)/s2.second;
	if(s1.first>=0&&s2.first>=0) {
		int a,b; int d=exgcd(s1.second,s2.second,a,b); b=-b;
		if((s2.first-s1.first)%d!=0) return ans;
		int T=s2.second/d; a=(a*(s2.first-s1.first)/d%T+T)%T;
		s1.first+=s1.second*a; s1.second*=T;
		ans+=(n-s1.first+s1.second)/s1.second;
	} return ans;
}
void work() {
	scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&z,&a,&l,&r);
	a%=z; x%=z; y%=z;
	pair<int,int> s1=work(x,a,z),s2=work(y,a,z);
	printf("%lld\n",calc(r,s1,s2)-calc(l-1,s1,s2));
}
signed main() {
	int _; for(scanf("%lld",&_);_--;) work();
}