CF1804C 题解

题目链接

今天好不容易有空更那就再更一篇（

一道很有意思的诈骗题，我会写出我的思考过程。

题意：（我的翻译）

一个转盘有 $n$ 个格子分别为 $0$ $1$ $2$ $\cdots$ $n-1$，初始时在 $x$ 号格子，你希望转动一次转盘来使它回到 $0$ 号位置，（转盘转到 $n-1$ 后再转就会回到 $0$）。

你有一个可以使出的最大力气 $p$，你可以使出任意的力气 $f$ 满足 $f\leq p$。然后，转盘会转动 $f$ 秒，第一秒转动 $f$ 个格子，第二秒转动 $f-1$ 个格子，以此类推，第 $f$ 秒就会转动 $1$ 个格子，之后转盘就会停止转动。

现在给你 $n$，$x$，$p$，请你判断能否使出一次一个力气 $f$，使得转盘能够转到 $0$ 号格子，$T$ 组数据，用 ``No`` 和 ``Yes`` 回答

数据范围：

$1\leq T\leq 10^4$

单组数据中 $n\leq 10^5$

所有数据中 $n$ 之和小于 $2\times 10^5$

$1\leq p\leq 10^9$

思路

首先想到枚举花多少力气，我们可以尝试这样枚举。$i$ 从 $1$ 枚举到 $p$，每一轮多转 $i$ 格。容易得出，转 $i$ 下时，转盘总共了 $1+2+\cdots +i$ 格，和使出 $i$ 的力气的效果相同。

推论 $1$：（显然成立）转 $i$ 格和转 $i \% n$ 的效果相同。

再来看刚刚枚举 $i=1\cdots p$ 的过程，假设 $n<p$，我们就可以发现这个枚举过程化简为了这样。转 $1$ 格，转 $2$ 格 $\cdots$ 转 $n-1$ 格，转 $n$ 格相当于转 0 格没用，所以转 $n+1$ 格，也就是再转 $1$ 格。

枚举过程变成了一个循环节，长度为 $n-1$，第 $i$ 项为 $i$，使用等差数列求和公式得一个循环节使转盘转动 $\frac{n\times (n-1)}{2}$ 格。

分类讨论，当 $n$ 为奇数时，我们发现一个循环节使转盘的转动效果为 $0$ 格，所以只要转动一个循环节，看看行不行即可。（注：此时转动 $i$ 个循环节再转 $j$ 下就相当于转 $j$ 下）

当 $n$ 为偶数时，我们发现一个循环节使转盘转动 $\frac{n}{2}$ 格，两个循环节就会使转盘转动 $0$ 格，所以只要枚举到两个循环节看下行不行即可。

因为是赛时代码有点慌所以稍乱：

#include <cmath>
#include <iostream>
#define int long long
using namespace std;
int t, n, x, p;
int sum, tmp;
signed main () {
    cin >> t;
    while (t --) {
        cin >> n >> x >> p;
        tmp = (1LL + n) * n / 2;
        if (n & 1) {
            bool f = false;
            for (int i = 1; i <= min (n, p); i ++) {
                if ( (x + i * (i + 1LL) / 2) % n == 0) {
                    f = true;
                    break;
                }
            }
            if (!f) cout << "No" << "\n";
            else cout << "Yes" << "\n";
        }
        else {
            bool f = false;
            for (int i = 1; i <= min (n, p); i ++) {
                if ( (x + i * (i + 1LL) / 2) % n == 0) {
                    f = true;
                    break;
                }
            }
            if (p > n) {
                p -= n;
                if (x >= n / 2) x -= n / 2;
                else x += n / 2;
                for (int i = 1; i <= min (n, p); i ++) {
                    if ( (x + i * (i + 1) / 2) % n == 0) {
                        f = true;
                        break;
                    }
                }
            }
            if (!f) cout << "No" << "\n";
            else cout << "Yes" << "\n";
        }
    }
    return 0;
}