問題はこちら
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