20191101 csp-s模拟T1（数学问题）

T1 曾经排队

1.1 题目背景 他是一匹棕色的马。 他在奔跑，和一群马一起奔跑。 他还记得出发前，头马壮烈的嘶鸣，以及众马沸腾的银河一般的呐喊。 他远远的，视线绕过头马，看向远方。 他记得自己什么光也没看到。

1.2 题目描述 出发前，群马要列队。 为了奔跑时方便管理，头马把这些马分成了$n$组，第i组有$c_i$匹马。 为了使队形更整齐，美观，他制定了一个必须满足的规定： 每一组都要排成几行。有一个统一给定的正整数$a$，每一行的马匹数都不能超过$a$，而且每一组中只能有最多一行马的数量不足a匹。 他还提出了如下两个要求： 1.每一行的马匹数都正好$a$匹。 2.对于任意一组，每行马匹数都必须严格小于行数（不可以等于）。 现在，头马想询问如果每一行有匹马，是否能满足第一或第二个要求。 由于他想确定最好看的方案，所以他会有$q$次询问。

1.3 输入格式 第一行一个正整数$n$，表示组数。 第二行$n$个正整数，第$i$个正整数$c_i$，表示第$i$组的马匹数。 第三行一个正整数$q$，表示询问数。 接下来$q$行，每行两个正整数$a,‬b$，表示每一行$a$匹马是否满足第$b$个规定（$b为1或2$）。

1.4 输出格式 共$q$行，第$i$行一个字符串$"Yes"或"No"$（不输出引号），表示第$i$个询问能否被满足。

1.5 输入样例 4 16 18 12 24 4 4 1 2 1 4 2 3 2

1.6 输出样例 No Yes No Yes

1.7 样例解释 第一个询问，如果每行$4$匹马，第二个方阵每行的马匹数就不可能相等，因此不满足第一个条件，输出$No$ 第二个询问，第一组可以排成$8$行，第二组可以排成$9$行，第三组可以排成$6$行，第四组可以排成$12$行，输出$Yes$ 第三个询问，第三组每行马匹数（即给定的$4$匹）多于行数，输出$No$ 第四个询问，每一组每行马匹数都严格小于行数，输出$Yes$

1.8 数据范围及约定 对于所有数据：$1\le n,q\le 7\times 10^5,1\le c_i,a\le 10^{18},1\le b\le 2$.

思路： 对于要求一，即$a$为所有数的$gcd$的因数。 对于要求二，即$a$小于最小数开方。

代码：

#include<bits/stdc++.h> using namespace std; #define in Read() #define LL long long #define re register inline char ch(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline LL in{ LL s=0,f=1;char x; for(x=ch();!isdigit(x);x=ch()) if(x=='-') f=-1; for( ;isdigit(x);x=ch()) s=(s<<1)+(s<<3)+(x&15); return s*f; } const LL A=1e6+5; LL n,q; LL s[A]; LL gcd,minn=1e18; LL two; LL a,b; inline LL find_gcd(LL x,LL y){ return y?find_gcd(y,x%y):x; } signed main(){ freopen("queue.in","r",stdin); freopen("queue.out","w",stdout); n=in; for(re int i=1;i<=n;++i) s[i]=in; gcd=s[1]; for(re int i=1;i<=n;++i){ gcd=find_gcd(gcd,s[i]); minn=min(minn,s[i]); } int k=sqrt(minn); two=((k*k==minn)?(k-1):(k)); q=in; for(re int i=1;i<=q;++i){ a=in,b=in; if(b==1) puts((gcd%a)?"No":"Yes"); if(b==2) puts((a>two)?"No":"Yes"); } return 0; }