Gym 102215C – Jumps on a Circle

题目链接:2019, XII Samara Regional Intercollegiate Programming Contest, C

题目要求对于$[0,n]$的每一个$i$的下面的同余方程是否有解:

$$ \frac{(x+1)x}{2} \equiv i \pmod{p}, x \in [0,n] $$

我们知道$b|a$时,有

$$\frac{a}{b} \bmod{p} = \frac{a \bmod {bp}}{b}$$

则我们可以把方程化成

$$ \frac{(x+1)x  \bmod{(2p)} }{2} = i  $$

而$x(x+1) \bmod{ 2p} = (x \bmod{2p})[(x+1) \bmod {2p}]$,由此可以看出$x$迭代$2p$次一定会循环,所以只要枚举$[0, \min\{ n, 2p\}]$即可。

 

说点什么

avatar
50
  Subscribe  
提醒