yukicoder : No.2280 FizzBuzz Difference

これは自力で行けた。
https://yukicoder.me/problems/no/2280

問題

正整数M,A,B,Kが与えられる。
M以下の、AまたはBの倍数である正整数を漏れなく昇順に並べた数列をXとする。
隣接要素の差がKとなっている箇所は何か所あるか。
なおA＜Bとする。

解法

• K＞Aの場合、解は0。Xは最大でもA以下の間隔のため。
• K=Aの場合、Aの倍数だけ並べると解はfloor(M/A)-1となる。そこに途中Aの倍数でなくBの倍数が挟まると、それだけ解が減るので、そのような要素数を求めればよい。
• K＜Aの場合、n*A+K=m*Bまたはm*B+K=n*Aとなるようなn,mの組み合わせを求めればよいので、それぞれのケースをCRTで求める。

int T;
ll M,A,B,K;

ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q)
	if(q==0) return x=1,y=0,p;
	ll g=ext_gcd(q,p%q,y,x);
	y-=p/q*x;
	return g;
}

pair<ll,ll> crt(ll a1,ll mo1,ll a2,ll mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2
	ll g,x,y,z;
	g=ext_gcd(mo1,mo2,x,y);
	a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2;
	if(a1%g != a2%g) return pair<ll,ll>(-1,0); // N/A
	__int128_t lcm=mo1*(mo2/g);
	if(lcm<mo1) return pair<ll,ll>(-2,0); // overflow
	if(x<lcm) x+=lcm;
	
	__int128_t v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g);
	return make_pair(((v%lcm)+lcm) % lcm,lcm);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>M>>A>>B>>K;
		ll g=__gcd(A,B);
		
		if(K>A||K%g) {
			cout<<0<<endl;
			continue;
		}
		A/=g;
		B/=g;
		K/=g;
		M/=g;
		ll ret=0;
		if(A==K) {
			M=M/A*A;
			ll numa=M/A;
			ll numb=M/B-M/(A*B);
			ret=numa-1-numb;
		}
		else {
			
			// nA+K=mB;
			auto p=crt(K,A,0,B);
			if(M>=p.first) ret+=(M-p.first)/p.second+1;
			p=crt(0,A,K,B);
			if(M>=p.first) ret+=(M-p.first)/p.second+1;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

本番中は細かいバグを取り切れず間に合わなかった。