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

メモ

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

yukicoder No.72 そろばん Med

問題はこちら
No.72 そろばん Med - yukicoder

前の問題と同じなので基本的な考え方は省略

先にnの剰余をとっておけば、平方しても8Byteの範囲で収まるが
n≡m mod pでもfloor(n*n/4)≡floor(m*m/4) mod pとは限らない
しかし
n≡m mod 2pならfloor(n*n/4)≡floor(m*m/4) mod pとなる!
(∵n=2kp+mとしたとき、n*n/4=pk*pk+pk+m*m/4)
ということで

int main(){
	long n,t=1e6+7;
	scanf("%ld",&n);
	n%=2*t;
	printf("%ld",(n*n/4+n)%t);
	return 0;
}

どん

long n,t=1e6+7;main(){n=scanf("%ld",&n)>printf("%ld",(n*n/4+n)%t,n%=t*2);}

74B