跳转至

剩下的数

题目大意

有 \(t\) 个测试。

给定一个范围 \([l, r]\)，然后再给定一个 \(m\) 代表要询问 \(m\) 次。

对于每一次询问，都会输入一个数 \(x\)，将范围 \([l, r]\) 的整数看成是一个环，寻找该环的某连续片段，使得该片段的和恰好是 \(x\) 的倍数，然后我们要删掉该片段，剩下的数还是要按顺序连成新的环，如果该环还能找到和为 \(x\) 的倍数的连续片段，就继续删除、拼接成新环，直到无法继续操作为止。

问操作停止之后，该环最少还会剩下多少个元素？

注意：\(0<x≤(r−l+1)\)

思路

将 \([l, r]\) 范围内的数进行求和得出 \(sum\) ，由于 \(0<x≤(r−l+1)\) ，所以 \(x\) 的倍数一定会出现 \([l, r]\) 里面，若对数组 \([l, r]\) 模于 \(x\) 得到一个新的数组 \(q\)，则数组 \(q\) 一定含有元素 \(0 \sim x - 1\)。

我们令：\(ans = sum \bmod x\)，如果 \(ans = 0\)，说明整个范围的和能被 \(x\) 整除，所以该环最终会剩下 \(0\) 个元素；

若 \(ans \neq 0\)，我们只需要在数组 \(q\) 中剔除 \(ans \neq 0\) ，那么剩下元素的和（在环内也照样连续）也一定可以被 \(x\) 整除，所以最终最少只会剩下一个元素。

代码参考 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define endl '\n'
#define pique priority_queue
#define oier \
            ios_base::sync_with_stdio(false);\
            cin.tie(nullptr); cout.tie(nullptr);
typedef long long LL;
typedef long double LD;
//typedef __int128_t int128;

const int inf = ~(1 << 31);  // 正无穷
const int ninf = (1 << 31);  // 负无穷

const LL infll = ~(1ll << 63); // 正无穷
const LL ninfll = (1ll << 63); // 负无穷

const int N = int (1e7 + 10);

/* ==========================代码区========================== */

LL t;
LL n, l, r, x;
LL ans;

inline LL f(LL a, LL b)
{
    return (a + b) * (b - a + 1) / 2;
}

void solve()
{ oier
    /* =========================== */

    cin >> t;
    while (t --)
    {
        cin >> l >> r >> n;
        ans = f(l, r);
        while (n --)
        {
            cin >> x;
            if (ans % x) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }

    /* =========================== */
}

/* ==========================代码区========================== */

/**
*                             _ooOoo_
*                            o8888888o
*                            88" . "88
*                            (| -_- |)
*                            O\  =  /O
*                         ____/`---'\____
*                       .'  \\|     |//  `.
*                      /  \\|||  :  |||//  \
*                     /  _||||| -:- |||||-  \
*                     |   | \\\  -  /// |   |
*                     | \_|  ''\---/''  |   |
*                     \  .-\__  `-`  ___/-. /
*                   ___`. .'  /--.--\  `. . __
*                ."" '<  `.___\_<|>_/___.'  >'"".
*               | | :  `- \`.;`\ _ /`;.`/ - ` : | |
*               \  \ `-.   \_ __\ /__ _/   .-` /  /
*          ======`-.____`-.___\_____/___.-`____.-'======
*                             `=---='
*          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
*                     佛祖保佑        永无BUG
*            佛曰:
*                   写字楼里写字间，写字间里程序员；
*                   程序人员写程序，又拿程序换酒钱。
*                   酒醒只在网上坐，酒醉还来网下眠；
*                   酒醉酒醒日复日，网上网下年复年。
*                   但愿老死电脑间，不愿鞠躬老板前；
*                   奔驰宝马贵者趣，公交自行程序员。
*                   别人笑我忒疯癫，我笑自己命太贱；
*                   不见满街漂亮妹，哪个归得程序员？
*/

int main()
{
    solve(); return 0;
}