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

メモ

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

yukicoder No.152 貯金箱の消失

問題はこちら
No.152 貯金箱の消失 - yukicoder

3数の和がL/4以下であるような原始ピタゴラス数を探す問題
ピタゴラスの定理 - Wikipediaなどに書かれている式によれば、原始ピタゴラス数は、互いに素で偶奇が異なる正整数n<mの組と(2mn, m^2−n^2, m^2+n^2)によって1対1に対応する
なので条件にあうn,mを探す事を考える。
この時の和は2mn+2mmなので、これがx以下であるためにはm<√(x/2)が必要
mを決めるごとに「2mn+2mm≦L/4かつ、n<mかつ、n,mは互いに素かつ、n,mは偶奇が異なる」を満たすnに対し、条件に合うピタゴラス数が1対1に対応するので、このようなnの個数を求めて合計すれば良い
L≦10^7なのでn,mに関して二重ループすれば間に合う
L=10^7の最大ケースでも、実際の場合の数は175570となるのでmodはいらない

int cop(int n,int m){return m?cop(m,n%m):n==1;}
//nとmが互いに素なら1を、さもなくば0を返す関数
//(gcdの計算の最後で最大公約数自身ではなく「最大公約数が1か?」を返している)
int main(){
	int n,m,L,s=0;
	scanf("%d",&L);
	L/=4;
	for(m=2;m*m<L;m++)for(n=1-m%2;2*m*n+2*m*m<=L&&n<m;n+=2)s+=cop(n,m);
	//nはmの偶奇に応じて0か1から初めて2ずつ増やす
	printf("%d",s);
	return 0;
}

copの中でsをincすれば返り値はいらないっぽい
Lを4でわらなくても、mのループの終了条件はそのまま、nの方は適当に書き換えることでうまくいく
1-m%2 は ~m&1 と書くことができる

n,L,s;
p(n,m){!m?s+=n==1:p(m,n%m);}
main(m){
	for(scanf("%d",&L);++m*m<L;)for(n=~m&1;n<m&n<=L/8/m-m;n+=2)p(n,m);
	s=!printf("%d",s);
}

127B


17/01/30追記
C++のやたら短いコードを見つけた
#112043 No.152 貯金箱の消失 - yukicoder
「互除法を逆からやれば単なる再帰で書ける」という発想らしい
具体的には(x,y)=(2,1)からスタートし、(x+y,x),(x+y,y)へ遷移していくと、x>yかつgcd(x,y)=1なる(x,y)の組を全て辿ることができる
ということで、これをパクって参考にして、短縮を目論む

L;
f(x,y){return 8*x*(x+y)<=L?(x+y)%2+f(x+y,x)+f(x+y,y):0;}
//x,yの偶奇が異なる⇔(x+y)%2が1
main(){
	scanf("%d",&L);
	printf("%d",f(2,1));
	return 0;
}

これをぎゅっとして

L;
f(x,y){return 8*x*(x+=y)>L?0:x%2+f(x,x-y)+f(x,y);}
main(){L=!printf("%d",f(2,scanf("%d",&L)));}

96B

returnの後ろの空白を省略しようとしたが、これではWA(95B)

L;
f(x,y){return(x+y)*x*8>L?0:f(x+=y,x)+f(x,y)+x%2;}
main(){L=!printf("%d",f(2,scanf("%d",&L)));}

returnを書かないようにしても同じ長さになった

L,s;
f(x,y){L/8/x/(x+=y)?f(x,x-y),f(x,y),s+=x%2:0;}
main(){L=!printf("%d",s,f(2,scanf("%d",&L)));}