読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.316 もっと刺激的なFizzBuzzをください

問題はこちら
No.316 もっと刺激的なFizzBuzzをください - yukicoder

1以上N以下の整数であって、a,b,cの倍数であるものからなる集合をそれぞれA,B,Cとおくとき
#(A∪B∪C)を求めるのが今回の問題
包除原理から(あるいはベン図をぐっと睨んで)
#(A∪B∪C)=#A+#B+#C-#(A∩B)-#(B∩C)-#(C∩A)+#(A∩B∩C)
が一般の集合A,B,Cに対して成立する
#Aは簡単で、「1以上N以下でaの倍数であるものの個数」なのでfloor(N/a)
#B,#Cも同様。
(A∩B)は「~でaの倍数かつbの倍数であるもの」であり、「aの倍数かつbの倍数⇔lcm(a,b)の倍数」なので#(A∩B)=floor(N/lcm(a,b))
(lcmは最小公倍数を表す)
同様にして#(A∩B∩C)=floor(N/lcm(a,b,c))

一般に
lcm(a,b)=a*b/gcd(a,b)
lcm(a,b,c)=lcm(lcm(a,b),c)
が成立するので、これを用いて求めることができる

long gcd(long a,long b){return b?gcd(b,a%b):a;}
long lcm(long a,long b){return a*b/gcd(a,b);}
int main(){
	long n,a,b,c,s=0;
	scanf("%d%d%d%d",&n,&a,&b,&c);
	s=n/a+n/b+n/c-n/lcm(a,b)-n/lcm(b,c)-n/lcm(c,a)+n/lcm(lcm(a,b),c);
	//lcm(a,b,c)は最大でa*b*cになるので、intだとオーバーフローの可能性がある
	printf("%d",s);
	return 0;
}

lcmの関数を作らずに、最後の計算も途中でaを書き換えることでまとめて

long n,b,c;
g(a,b){return b?g(b,a%b):a;}
main(a){
	scanf("%d%d%d%d",&n,&a,&b,&c);
	n=!printf("%d",n/a+n/b+n/c-n*g(a,b)/a/b-n*g(c,b)/b/c-n/(a*=c/g(a,c))+n*g(a,b)/a/b);
}

161B

aとnを入れ替えて

long a,b,c;
g(a,b){return b?g(b,a%b):a;}
main(n){
	scanf("%d%d%d%d",&n,&a,&b,&c);
	a=!printf("%d",n/a+n/b+n/c-n*g(a,b)/a/b-n*g(c,b)/b/c-n/(a*=c/g(a,c))+n*g(a,b)/a/b);
}

だとWAになる… 闇だ…