首页 > 试题广场 >

剩下的数

[编程题]剩下的数

热度指数：1827 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个由 $l…r$ 共 $r-l+1$ 个整数组成的环。

牛妹对这个数环进行了 $m$ 次询问，每次给定一个整数 $x$ 问牛牛操作到不能继续操作时最少会剩下几个数。

每一次操作，牛牛都会选择环上一段（可以是整个环），这一段数的和应该为 $x$ 的倍数，然后牛牛就会删去这一段，同时把剩下的数按顺序重新连成一个环。

输入描述:

本题采用多组案例输入，第一行一个整数  代表案例组数。
每组案例中，第一行输入两个空格分隔的整数： 。
接下来一行输入一个整数  。
接下来  行，每行输入一个数  代表询问。
保证：


单个测试点中所有案例  的和不超过

输出描述:

对于每组案例，输出共  行，每行一个整数代表牛妹询问的答案。

示例1

输入

输出

1
0

算法知识视频讲解

EAHUO

关于近期题面描述质量的反馈

忍不住要吐槽一下最近的题面质量，实在是差强人意。

逻辑不严谨：今天的数环问题，对于“多次询问是否基于初始状态”这一核心逻辑避而不谈。虽然大家能猜到是独立的，但作为算法题，这种描述是否严重失职了呢？
语法不通顺：前几天的“智数”题，那句“给升序排序第k个智数”简直让人一时间看不懂，就好像是机翻英语一样。

题面是沟通的桥梁，如果连基本的清晰准确都做不到，只会让做题体验大打折扣。希望官方能尽快提升审核标准，提高题面质量，减少做题人在读题上浪费的时间。

发表于 2025-12-17 09:29:01 回复(2)

C++

Reisentyan

我们将使用拉马努金瞪眼法解决这一题

特别注意， $0<=x<=(r-l+1)$

注意到，如果 $x>(l+r)*(r-l+1)/2$ ，则一个都无法减少，答案为 $r-l+1$

否则，如果 $((l+r)*(r-l+1)/2)\%x =0$ ，则答案为 0

否则答案为 1

证明：

如果 x 确实比总和要大，无论如何都凑不出 x 的倍速

如果总和比 x 大，且无法整除，则我们可以找到 $ax+sum\%x$ ，其中 a 为某个常数。

只不删这一个数字，其他的数字加起来可以被 x 整除，这个数字是否存在？

因为 x 的限制，x 只能为 $[0,r-l+1]$ 中间的一个数，当然不能为 0

这 r-l+1个数字 %x 对应了 r-l+1 个不同的余数（当然啦，这些数字是连续的）

也就是说，对应的余数的范围在 $[0,x-1]$ 之间

换句话说，就是 x 的所有可能的余数都存在，就可以选取那个特殊数字了

证毕。

注意到，代码要写成这样：

void solve()
{
	ll l = q_;
	ll r = q_;
	int m = q_;
	ffp(i, 1, m)
	{
		ll x = q_;
		ll sum = ((l + r) * (r - l + 1)) >> 1;
		if (x > sum)
		{
			cout << r - l + 1 << '\n';
			continue;
		}
		cout << ((sum % x) == 0 ? 0 : 1) << '\n';
	}
}

int main()
{
	int t = q_;
	while (t--)
	{
		solve();
	}

	return 0;
}


/*
⡀⠎⠀⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⣄⠃⠈⣶⡛⠿⠭⣉⠛⠿⡿⠛⠉⣀⣠⣤⣭⡏⠴⢀⣴⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣷⣱⣬⠛⠉⠀⠀⢠⠀⠀⠀⢀⣀⠀⠉⠿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠈⡿
⠀⠀⠀⠀⠀⠀⠀⢀⢿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⡏⠀⠀⠀⠀⠈⠳⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⠋⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠀⣸⠀⣿⣿⣿⣿⠟⠀⠀⠀⠂⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠈⡀⠀⠀⠀⠻⣿⣿⣿⣿⣷⡀⠘
⠀⠀⠀⠀⠀⠀⠀⣧⣿⣿⣿⣿⠋⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠙⣿⣿⣿⣿⣿⣄⣧
⠀⠀⠀⠀⠀⠀⣸⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⠀⠈⢿⣿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⢂⠻⣿⣿⣿⣿⣿⣄
⠀⠀⠀⠀⠀⣿⣿⣿⣿⣹⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⡄⠈⢿⣿⣿⣿⣿⣆
⠀⠀⠀⠀⣿⣿⣿⣿⠁⡇⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀⠐⠸⠀⠀⠻⣿⣿⣿⣆⢦
⠀⠀⢠⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡏⣧⠀⠀⠀⠀⠐⣇⠀⠀⠙⣿⣿⣿⡄⠙⣄
⠀⣴⣿⣿⣿⣿⠏⠀⢸⠀⠀⠀⠀⠀⠀⡿⢿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣃⣈⣦⠀⠀⠀⠀⢹⠀⠀⠀⠸⣿⣿⣿⠀⠀⠳⣀
⠋⣸⣿⣿⣿⡟⠀⠀⠀⡆⠀⠀⠀⠀⠀⡏⠙⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⠀⠀⠀⢧⠀⠀⠀⠀⡇⠀⠀⠀⠘⣿⣿⣷⠀⠀⠘
⠀⣿⣿⣿⢩⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⣀⠀⢱⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠂⢀⣴⣶⣿⣿⡀⠀⠀⢻⠀⠀⠀⠀⠹⣿⣿⡄
⢸⣿⣿⠃⠈⠀⠀⢸⠀⣿⣆⠀⠀⠀⠀⣿⣿⣿⠷⠘⡀⠀⠀⠀⠀⠀⠀⢠⢹⡀⠈⡿⠻⣿⣛⢿⣿⣷⡀⠈⠀⠀⠀⠀⠀⢻⣿⣿
⣿⣿⣿⠀⠀⠀⠀⢸⠀⡇⣼⣄⠀⠀⠀⢻⣿⡄⠑⠑⣿⡀⠀⠀⠀⢀⠀⠂⠇⠀⠀⠖⠛⢿⣿⣿⣌⢿⣿⣿⡆⠀⠀⠀⠀⠀⣿⣿⡀
⣿⣿⡇⠀⠀⠀⠀⢸⠀⣾⣿⣿⡷⠿⣷⣤⣿⣿⡄⠀⠀⠀⠑⠤⡀⠀⠃⠀⠀⠀⠀⣿⣶⣿⣿⣿⣿⣆⠙⣿⣧⠀⠀⠀⠀⠀⣿⣿⡇
⣿⣿⠁⠀⠀⠀⠀⠘⣾⣿⣿⠁⣴⣿⣿⣿⣿⣿⣇⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠸⡏⠙⣿⠉⠻⣿⠀⠀⣿⠀⠀⠀⣄⠀⣿⢸⣷
⣿⣿⡇⠀⠀⠀⠀⠀⣿⣿⠁⠀⣿⣿⠋⣿⠏⠙⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⢀⢻⠀⠀⢀⡟⢀⣿⣸⢃⠟
⣿⣿⣿⠀⡄⠀⠀⠀⠘⠻⡄⠀⢹⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡘⠀⢀⣿⠃⣿⣿⡗⠁
⣧⣿⣿⣧⢹⡀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⣴⣿⣿⣾⣿⣿⣿
⢿⠘⣿⣿⣿⣿⣤⠀⠢⡀⠱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣵⣿⣿⣿⣿⣿⣿⣿⣿⣷
⠀⠉⣿⣿⣿⡿⣿⠻⣷⣬⣓⣬⣄⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠉⠈⠈⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⠃⠼⢉⣿⣿⣿⣿⣿⣿⣿
⠀⠀⣿⣿⣿⣷⠀⠀⠀⠘⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⡏⠀⠀⢸⠀⢻⢿⣿⣿⡏⣿
⠀⢸⣿⣿⣿⣿⠀⠀⠀⠀⢻⣿⣿⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣴⣾⣿⣿⣿⣿⠀⠀⠀⢸⠀⠀⢸⣿⣿⠘⡀
⢦⡿⣿⣿⣿⢿⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣶⣶⣦⡄⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠘⡄⠀⠈⣿⣿⡄⠱
⣴⠛⣾⣿⣿⢸⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⡄⠀⠀⠀⠀⠀⠀⠀⣯⠛⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⣇⠀⠀⣿⣿⣿
⠿⠀⣿⣿⣿⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⠟⠰⡾⠃⠀⠀⠀⠀⠀⠀⠀⠙⡟⠀⢻⣿⣿⣿⣿⣿⡆⠀⠀⠀⠸⠀⠀⠸⣿⣿⣷
⠆⢳⣿⣿⡇⠀⠀⠀⠀⠀⠀⣿⣿⣿⠛⠿⠿⢿⡟⠀⠀⠉⠦⣀⡤⢶⠀⠖⠲⠶⠊⠀⠀⠀⢻⡛⠛⠛⣿⣿⠀⠀⠀⠀⠃⠀⠀⢿⣿⣿
*/

编辑于 2025-12-17 10:51:25 回复(2)

周康禧

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
const int N=5e5+10;
const int M=2e5+10;
// const int mod = 1000000007;
const int mod = 998244353;
//随机化
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> Tp(1, 1000000000);
// cout<<fixed<<setprecision(10);



void solve(){
    ll l,r;
    cin>>l>>r;
    int q;
    cin>>q;
    ll sum=((l+r)*(r-l+1))/2;
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        if(sum%x==0){
            cout<<0<<'\n';
        }else{
            cout<<1<<'\n';
        }
    }
    
    
    
}   
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

注意x的数据范围，r-l+1一定大于等于x，那么就说明在l到r的这个区间中一定具备取模得到0~x-1的完全剩余周期，即每有x个连续的数字就会有一个取模 0 ，1，2，...，x-1的循环（第一个不一定是0，但是最后集合都是一样的）

那么我们考虑如果能全部选就是总和对x取模为0，如果不满足就去掉l到r中任意一个sum%x同余的数字就行了，所以结果只会是0或者1

发表于 2025-12-17 15:37:44 回复(1)

自由的风0450

题目说“把剩下的数按顺序重新连成一个环”，但在做题时发现每一次操作都是独立的。那为什么要有这一句充满误导性的话？

发表于 2025-12-17 10:39:38 回复(0)

提交观点

问题信息

难度：

4条回答 9收藏 516浏览

剩下的数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题