剩下的数【牛客tracker 每日一题】

剩下的数

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

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

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

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

输入描述：

本题采用多组案例输入，第一行一个整数T TT代表案例组数。
每组案例中，第一行输入两个空格分隔的整数：l llr rr。
接下来一行输入一个整数m mm。
接下来m mm行，每行输入一个数x xx代表询问。
保证：
0 < l < r < 1 0 9 0<l<r<10^90<l<r<109
0 < x ≤ ( r − l + 1 ) 0<x≤(r−l+1)0<x≤(r−l+1)
单个测试点中所有案例m mm的和不超过1 0 5 10^5105

输出描述：

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

示例1

输入：

1 1 5 2 2 3

输出：

1 0

解题思路

首先计算l ll到r rr的整数和s u m sumsum（利用等差数列求和公式s u m = ( l + r ) ∗ ( r − l + 1 ) / 2 sum=(l+r)*(r-l+1)/2sum=(l+r)∗(r−l+1)/2，避免逐个数累加，适配l ll、r rr达1 e 9 1e91e9的规模），对于每组案例的每个询问x xx，核心依据环结构的操作特性判断结果：若s u m sumsum是x xx的倍数，说明可将整个数环作为一段删去，最终剩下0 00个数；若s u m sumsum不是x xx的倍数，由于无法删完所有数，操作到不能继续时最少剩下1 11个数；该方法单次查询仅需一次模运算，时间复杂度为O ( 1 ) O(1)O(1)，适配单个测试点中m mm的和达1 e 5 1e51e5的大规模查询，无需复杂操作模拟，直接通过数学判断精准输出每个询问的结果。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll t;cin>>t;ll sum=0;while(t--){ll l,r,m;cin>>l>>r>>m;sum=(l+r)*(r-l+1)/2;while(m--){ll x;cin>>x;if(sum%x==0)cout<<0<<endl;elsecout<<1<<endl;}}return0;}