yukicoder No.648 お や す み

問題はこちら
No.648 お や す み - yukicoder

1からmまでの和はm(m+1)/2になるので「m(m+1)/2=nとなるmが存在するか？」と同じ問題になる。
とりあえず誤差の問題は置いておく。
もしそのようなmが存在したとする。
√(m(m+1))=√(2n)となる。ここでm＜√(m(m+1))＜m+1なので、floor(√(2n))=mとなることが分かる。
結局「m=floor(√(2n))としたとき、m(m+1)/2=nとなるか？」と同じ問題であることが分かる。
（答えがNOの時はどのようなmに対してもm(m+1)/2=nは成り立たないので、これでよい）
さて、誤差を考える。つまり、floor(√(2n))が正しく求まるかどうかを考える。
真の答えがNOである時に誤ってYESと答えることはない（どのようなmに対してもm(m+1)/2=nは成り立たないので）
真の答えがYESである時を考える。
このとき√(2n)はm+0.5くらいになるので、n＜2*10^18つまりm＜2*10^9だと相対誤差10^-10≒2^-34くらいまでは許される。
2nをdoubleにキャストするとき、平方根を計算するときに発生する誤差はそれぞれ高々2^-52程度なので、これは結果に影響を与えない。
よって誤差が影響を及ぼすことはない。

long n,m;
main(){
	scanf("%ld",&n);
	m=sqrt(2*n);
	if(m*(m+1)/2==n)printf("YES\n%d",m);
	else printf("NO");
}

ぎゅっとする

long n,m;
main(){
	scanf("%ld",&n);
	printf(n+m*~m/2?"NO":"YES\n%d",m=sqrt(2*n));
}

77B