商洛网站建设,ui设计技术培训培训班,wordpress知更鸟菜单修改,品牌网站制作简创网络链接#xff1a;https://ac.nowcoder.com/acm/problem/244138 来源#xff1a;牛客网
题目描述 牛牛有一个由 l … r l…r l…r 共 r − l 1 r−l1 r−l1 个整数组成的环。 牛妹对这个数环进行了 m m m 次询问#xff0c;每次给定一个整数 x x x 问牛牛操作到不能继续…链接https://ac.nowcoder.com/acm/problem/244138 来源牛客网
题目描述 牛牛有一个由 l … r l…r l…r 共 r − l 1 r−l1 r−l1 个整数组成的环。 牛妹对这个数环进行了 m m m 次询问每次给定一个整数 x x x 问牛牛操作到不能继续操作时最少会剩下几个数。
每一次操作牛牛都会选择环上一段可以是整个环这一段数的和应该为 x x x 的倍数然后牛牛就会删去这一段同时把剩下的数按顺序重新连成一个环。
输入描述: 本题采用多组案例输入第一行一个整数 T T T 代表案例组数。 每组案例中第一行输入两个空格分隔的整数 l r l r lr 。 接下来一行输入一个整数 m m m 。 接下来 m m m 行每行输入一个数 x x x 代表询问。 保证 0 l r 1 0 9 0lr10^9 0lr109 0 x ≤ ( r − l 1 ) 0x≤(r−l1) 0x≤(r−l1) 单个测试点中所有案例 m m m 的和不超过 1 0 5 10^5 105
输出描述: 对于每组案例输出共 m m m 行每行一个整数代表牛妹询问的答案。
示例1 输入
1
1 5
2
2
3输出
1
0此题中 l l l和 r r r都小于 1 e 9 1e9 1e9所以大概率是一道依靠找规律或者数学的题目而且看到样例的输出中仅仅包含 1 1 1和 0 0 0的时候就应该质疑一下该题目是否有一些特殊性。 首先来看第一种情况 如果这个数环的所有组成的数加起来的总和就是所提出的询问的倍数那么答案就很明确了在这种情况下我们可以在第一步直接删掉所有的数那么就余下了 0 0 0个数也就是最终的答案。满足这种情况的条件就是 所有数的总和 m o d x 0 mod x 0 modx0 然后是第二种情况 如果这个数环所有数的加和不是所提出询问的数的倍数那么答案就肯定是 1 1 1也就是最终能余下的最小组成个数就是 1 1 1。
首先 x x x的取值范围为 0 x ( r − l 1 ) 0 x (r - l 1) 0x(r−l1)换句话说 x x x只能取到大于 0 0 0且小于等于数环的组成个数的数比如样例中 l l l为 1 1 1 r r r为 5 5 5那么这个数环就是由 1 2 3 4 5 12345 12345这五个数组成的那么x的取值范围就是 0 x 5 0 x 5 0x5。
先来分析观察一下样例
x 1时从 l l l到 r r r
1 % 1 0 2 % 1 0 3 % 1 0 4 % 1 0 5 % 1 0x 2时
1 % 2 1 2 % 2 0 3 % 2 1 4 % 2 0 5 % 2 1x 3时
1 % 3 1 2 % 3 2 3 % 3 0 4 % 3 1 5 % 3 2x 4时
1 % 4 1 2 % 4 2 3 % 4 3 4 % 4 0 5 % 4 1x 5时
1 % 5 1 2 % 5 2 3 % 5 3 4 % 5 4 5 % 5 0这时候我们发现每次 m o d mod mod都能够取得 0 0 0到 x − 1 x-1 x−1的所有数。当然这种情况是建立在 0 x ( l − r 1 ) 0 x (l-r1) 0x(l−r1)的情况下如果x再等于 6 6 6的话就无法取到0了。
所以就找到了一个规律由于 0 x ( l − r 1 ) 0 x (l -r 1) 0x(l−r1)如果让l到r之间的所有数去 m o d x mod x modx一定能够得到 0 0 0到 x − 1 x-1 x−1中的所有数。 如果 l l l到 r r r的加和不是 x x x的倍数的话比如说 x 4 x 4 x4的时候l到r所有数的加和为 15 15 1515 1515 % 4 3 4 3 43可以发现 3 3 3 % 4 3 4 3 43 15 − 3 12 15 - 3 12 15−312 % 4 0 4 0 40所以我们就可以让 3 3 3这个数留下删去其他的所有数这时候就可以只留下 1 1 1个数。
推广到其他情形的话因为 l l l到 r r r之间对 x x x取模一定能够取得 0 0 0到 x − 1 x-1 x−1中的所有的数加入加和对 x x x取模得到了一个部位 0 0 0的数 a a a根据取模的性质这个 a a a肯定是小于 x x x的那么就一定可以在 l l l到 r r r中找到一个数满足这个数对 x x x取模同样也能取得 a a a那么就一定可以删掉这个数之后使得数环剩下的数的加和能够为 x x x的倍数。
代码
#includeiostream
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin t;while(t--){long long l,r;cin l r;long long sum (r - l 1)*l (r - l 1)*(r - l)/2; //等差数列求和公式int m;cin m;while(m--){int x;cin x;if(sum % x 0){printf(0\n);}else{printf(1\n);}}}return 0;
}不过为什么l和r也要开long long才能过明明都小于1e9…
