C. Pull Your Luck

지문만 드럽게 쳐길게 써놨는데

x+p(p+1)2≡0(modn) x+\dfrac{p(p+1)}{2} \equiv 0 \pmod n

인 pp 가 존재하는지를 찾는 문제이다.

∑i=12ni=n(2n+1)\displaystyle \sum_{i=1}^{2n}i=n(2n+1) 이기 때문에 nn은 11부터 2n2n까지 다더한걸로 무조건 나뉜다.

그니까 pp를 1→2n1 \to 2n 까지만 검사해줘도 무방하다.

그 후로는 주기적으로 p(p+1)/2(modn)p(p+1)/2 \pmod n 이 동일하게 반복되기 때문이다.

void solve() {
   int n, x, p;
   cin >> n >> x >> p;
 
   for (int i = 1; i <= min(n * 3, p); i++) {
      int t = (i * (i + 1) / 2) % n;
      if ((x + t) % n == 0) {
         cout << "yes\n";
         return;
      }
   }
   cout << "no\n";
}

Comments

You may also enjoy