链接：https://ac.nowcoder.com/acm/contest/548/A
来源：牛客网
题目描述
这次 Tachibana Kanade 来到了一个神奇的学校参观，她发现了一些有趣的事情。这个学校的所有人脾气都十分的古怪：每个人都有两个属性 aiai 和 bibi，每个人都想和除他以外所有 j 满足 ai+bi=ajai+bi=aj 的人搞好关系。我们定义一对人的关系是好的，当且仅当这两个人互相想与对方搞好关系。
现在给出这 n 个人的属性，Tachibana Kanade 想知道，这些人会不会有至少一对人的关系是好的。
输入描述:
第一行输入一个整数 n ，表示人的个数。
接下来 n 行，每行两个整数 ai,biai,bi，意义如「题目描述」所述。
输出描述:
如果存在至少一对人的关系是好的，那么输出 `YE5`，否则输出 `N0`。示例1
输入
复制5 2 -10 3 10 0 5 5 -5 10 1
输出
复制YE5
说明
第三个和第四个人关系好。
简单的枚举题。
直接 O(n2)O(n2) 枚举每对人判断是否成立即可。
注意到输出的字符串为 YE5 和 N0 即可通过此题。
#include<iostream>
using namespace std;
int a[105][3];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i][0]>>a[i][1];
a[i][2]=a[i][0]+a[i][1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
if(a[i][2]==a[j][0]&&a[j][2]==a[i][0]){
cout<<"YE5"<<endl;
return 0;
}
}
}
}
cout<<"N0"<<endl;
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/548/B
来源：牛客网
题目描述
立华奏在学习初中数学的时候遇到了这样一道大水题：“设箱子内有 n 个球，其中给 m 个球打上标记，设一次摸球摸到每一个球的概率均等，求一次摸球摸到打标记的球的概率”
“emmm...语言入门题”
但是她改了一下询问方式：设最终的答案为 p ,请输出 p 小数点后 K1K1 到 K2K2 位的所有数字（若不足则用 0 补齐）
输入描述:
第一行一个整数 T,表示有 T 组数据。
接下来每行包含四个整数 m,n,K1,K2m,n,K1,K2，意义如「题目描述」所示。
输出描述:
输出 T 行，每行输出 K2−K1+1K2−K1+1 个数，表示答案。示例1
注意同行的数字中间不需要用空格隔开。
输入
复制5 2 3 2 3 1 7 1 7 2 5 1 3 12345 54321 3 10 12345 54321 100000 100010
输出
复制66 1428571 400 72601756 78428232175
备注:
1≤m≤n≤109,1≤K1≤K2≤1091≤m≤n≤109,1≤K1≤K2≤109；
0≤K2−K1≤105,T≤200≤K2−K1≤105,T≤20。
作者：RainAir
链接：https://ac.nowcoder.com/discuss/173818
来源：牛客网
简单的模拟题。
题目等价于求分数 ab 的小数点后 K1到 K2位的所有数字。
直接暴力模拟除法过程是肯定会 T 的，但是我们发现我们不用从头开始模拟，只需要从 K1K1 位开始模拟就可以了。
直接通过快速幂+取模算出第 K1 位的数字。然后我们发现 K2−K1≤105，所以暴力枚举除法过程就可以。
时间复杂度 O(n)。
因为m<n，小数点后第i位是(m*10^i)%n
先快速幂求到x-1位，再枚举就可以了，我又傻逼了
#include<iostream>
using namespace std;
long long int n,m,t,x,y;
long long quick(long long a,long long b,long long c){
long long ans=m;
while(b){
if(b&1) ans=(ans*a)%c;
a=(a*a)%c;
b>>=1;
}
return ans;
}
int main(){
cin>>t;
while(t--){
cin>>m>>n>>x>>y;
m=quick(10%n,x-1,n);
for(x;x<=y;x++){
m*=10;
cout<<m/n;
m%=n;
}
cout<<endl;
}
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/548/C
来源：牛客网
题目描述
立华奏是一个刚刚开始学习 OI 的萌新。最近，实力强大的 QingyuQingyu 当选了 IODS 9102 的出题人。众所周知， IODS 是一场极其毒瘤的比赛。为了在这次比赛中取得好的成绩，立华奏决定学习可能考到的每一个知识点。
在 QingyuQingyu 的博客中，立华奏得知这场比赛总共会考察选手 n 个知识点。此前，立华奏已经依靠自学学习了其中 k 个知识点。接下来，立华奏需要学习其他的知识点，每学习一个单独的知识点，需要消耗的时间为 TiTi 天。同时，某些知识点之间存在联系，可以加速学习的过程。经过计算，立华奏一共发现了其中 m 种联系，第 i 种联系可以表示为(Xi,Yi,Hi)(Xi,Yi,Hi)，其含义为“在掌握了第 XiXi 个知识点和第 YiYi 个知识点中任意一个后，学习 HiHi 天即可掌握另一个知识点”。
留给立华奏的时间所剩无几，只有 t 天，因此，她想知道自己能不能在这 t 天内学习完成所有的知识点。
输入描述:
本题输入量较大，请注意使用效率较高的读入方式接下来一行，包含 n 个整数，依次表示 T1,T2,⋯,TnT1,T2,⋯,Tn
输入的第一行包含四个整数 n, m, k, t，含义见上所述。
接下来一行，包含 k 个整数，表示立华奏已经学习过的知识点。如果 k=0，则此处为一空行。
接下来 m 行，每行 3 个整数 Xi,Yi,HiXi,Yi,Hi，描述一种联系。
输出描述:
如果立华奏能够学习完所有的知识点，输出一行 Yes。否则输出 No示例1
输入
复制4 3 2 5 4 5 6 7 2 3 1 2 3 1 3 2 3 4 2
输出
复制Yes
说明
立华奏已经学习过了第 2, 3 个知识，由第 2 个关系，立华奏可以花 2 天学会知识点 1，在由关系 3， 立华奏可以 2 天学会知识点 4，因此总共需要花费 4 天，可以完成任务。示例2
输入
复制5 4 0 12 4 5 6 7 1 1 2 3 1 3 2 3 4 2 1 5 233
输出
复制Yes
说明
立华奏比较菜，因此什么都没有学过。她可以选择先花 4 天的时间学会知识点 1。然后根据关系 1, 2，分别花 3, 2 天的时间学会知识点 2, 3，再根据关系 3，花 2 天的时间学会知识点 4。然后，她再单独学习知识点 5，花费1天，总共花费了 12 天 ，可以完成任务。
请注意，虽然关系 4 允许立华奏在知识点 1 的基础上学习知识点 5，但需要的时间比单独学习还要多，因此立华奏不会在知识点 1 的基础上学习知识点 5.
备注:
0⩽k⩽n⩽106,m⩽5×106,t⩽1018,Ti,Hi⩽103
作者：RainAir
链接：https://ac.nowcoder.com/discuss/173818
来源：牛客网
C. Review还不会，先标记一下
简单的图论题。
首先，我们考虑最简单的情况，即k=0k=0。然后，为了判定答案是否合法，我们考虑求出学完所有知识点的最小用时。考虑到一个知识点yy只能被下列两种途径学会：
- 单独学习这一个知识点，耗时TyTy
- 从某个已经学会的知识点xx中学习得来，耗时HxyHxy
如果我们新建一个“虚拟知识点”GG，并假设它刚开始便已经学会。那么，我们可以将第一种方案转化为第二种方案，即HGyHGy。而学会所有知识点，本质上就是将所有知识点联通，即求出原图的最小生成树即可。
下面，我们再考虑k>0k>0。我们可以再次使用虚拟节点GG，如果这个知识点初始时就已经学过，则只需要将其向虚拟节点GG连接一条边权为0的边，即可达到要求。
时间复杂度O((m+k)log(m+k))O((m+k)log(m+k))。
当然这时肯定会有人怒斥出题人“你的题怎么卡常啊”。
std写道这一步已经通过了，但考虑到一些选手可能没有写读入优化的习惯，因此我们可以进一步优化。
- 注意到每条边的边权在103103以内，因此我们可以将Kruskal算法中的快速排序改为计数排序，砍掉排序的一个log，
- 结合并查集的路径压缩与启发式合并，可以O((m+k)α(m+k))O((m+k)α(m+k))解决此题。
- 注意到如果在计算某一条边时，你所消耗的时间已经超过了 TT，那么可以直接跳过。
- 同理，注意到 t⩽1018t⩽1018 ，但是如果 tt 超过了 103×边数103×边数， 答案一定为
Yes
实际只需要第2个优化，便可以轻松通过此题。
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define MN 1000005
#define ll long long
#define MM 6000005
int n,m,k,c;ll t,ans;
int T[MN],f[MN];
int ff(int x){return f[x]?f[x]=ff(f[x]):x;}
struct edg{int u,v,w;}e[MM];
int read()
{
ll x=0;char s=getchar();
while(s<'0'||s>'9'){s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x;
}
int main(){
int x,y,z;
n=read(),m=read(),k=read();scanf("%lld",&t);
F(i,1,n)T[i]=read();
F(i,1,k)T[read()]=0;
F(i,1,n)e[++c]=(edg){n+1,i,T[i]};
F(i,1,m)x=read(),y=read(),z=read(),e[++c]=(edg){x,y,z};
sort(e+1,e+c+1,[](edg i,edg j){return i.w<j.w;});
F(i,1,c){
int u=ff(e[i].u),v=ff(e[i].v);
if(u!=v){
f[u]=v;
ans+=e[i].w;
}
}puts(ans<=t?"Yes":"No");
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/548/D
来源：牛客网
题目描述
立华奏是一个天天打比赛的 OIer。有一天，立华奏正在打一场比赛，菜爆了的立华奏依靠运气解决了大部分的题目，还有最后一道题目没有解决。
这道题目给定了两个长度为 n 的序列 {ai}, {bi}，要求两个长度为 n 的 0/1 序列 {ci}, {di}，最大化： min{∑ni=1aici,∑ni=1bidi}−∑ni=1ci−∑ni=1dimin{∑i=1naici,∑i=1nbidi}−∑i=1nci−∑i=1ndi
输入描述:
输入的第一行包含一个整数 n。
接下来一行，包含 n 个整数，表示序列{ai}
接下来一行，包含 n 个整数，表示序列{bi}
输出描述:
输出的第一行包含一个整数，表示式子的最大值。示例1
接下来一行，包含 n 个整数，表示你构造的序列 {ci}
接下来一行，包含 n 个整数，表示你构造的序列 {di}
如果有多种构造方法，你只需要输出任意一种。
输入
复制3 100000 -100000 100000 -100000 100000 -100000
输出
复制99998 0 0 1 0 1 0
备注:
n⩽105,|ai|,|bi|⩽105
作者：RainAir
链接：https://ac.nowcoder.com/discuss/173818
来源：牛客网
D.Sequence不会啊
简单的贪心题。最后一个测试点专门卡了一下n=0n=0可能让部分dalao的体验极差……出题人在此谢罪qwq
题目的含义其实是可以从{a},{b}{a},{b}中选出若干个数，选择一个数代价为11，你的利益为你{a}{a}和{b}{b}利益中的最小值。最大化你的利益。
我们记A=∑ni=1aici,B=∑ni=1bidi,K=∑ni=1ci+∑ni=1diA=∑i=1naici,B=∑i=1nbidi,K=∑i=1nci+∑i=1ndi，答案为min{A,B}−Cmin{A,B}−C
一个显然的贪心策略，是将两个序列从大到小排序，然后考虑A,BA,B中较小的那一个，从它所对应的序列（AA对应aiai,BB对应bibi）中选出最大的没有被选的一个数，将它选中，直到我们找不到一个大于11的数。
下面我们来考虑这种贪心的正确性。假设我们在{ai}{ai}中选择了k1k1个数ai1,ai2,⋯,aik1ai1,ai2,⋯,aik1，{bi}{bi}中选择了k2k2个数bj1,bj2,⋯,bjk2bj1,bj2,⋯,bjk2，记这种取数方案为G(I,J)G(I,J)，其中I={i1,i2,⋯,ik1},J={j1,j2,⋯,jk2}I={i1,i2,⋯,ik1},J={j1,j2,⋯,jk2}。由于{ai}{ai}，{bi}{bi}地位均等，因此我们不妨设A>BA>B。
假设另有一种取数方案G′(I′,J′)G′(I′,J′)比GG更优，则显然有I′⊂I,J′⊂JI′⊂I,J′⊂J。为什么？若存在一个下标，使得j∈J′j∈J′且j∉Jj∉J，则其一定选择了一个JJ中没有的
，使得bj−1>0bj−1>0，这与我们在选取中“直到我们找不到一个大于11的数”矛盾。同理，可证I′⊂II′⊂I
那么，由上可得，G′(I′,J′)G′(I′,J′)对应的方案，一定是从G(I,J)G(I,J)对应的方案中，将一些选择的数删去，使得答案更优。
-
若删去JJ中的某个数bjbj
则会使KK减少1，minA,BminA,B减少bjbj，答案会增加1−bj1−bj，但根据我们的取数方案，bj>1bj>1，因此答案会变得更差，与G′G′更优矛盾
-
若删去II中的某个数aiai
则会使KK减少1，AA减少aiai。根据我们的取数方案，我们每次都是从最小的收益对应的序列中选择的数，删去aiai后，不可能有A>BA>B。为什么？考虑到我们从大到小选取{ai}{ai}中的每一个数，且当且仅当A⩽BA⩽B时，才会选择{ai}{ai}中的数。显然，若删去aiai后A>BA>B，则我们不可能选择{ai}{ai}中的数，更不可能选择aiai。因此，必有$A<b$< span="">。但考虑到我们选取时，序列中均为整数，因此显然有A⩽B−1A⩽B−1，这使得minA,BminA,B至少减少了11，因此答案反而至少减少了00，因此答案不会变得更优。
综上，我们的贪心策略时正确的。
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define F2(i,a,b) for(int i=a;i<(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define MN 6000005
#define ll long long
int n,m,q,k;
int a[MN],b[MN],ap[MN],bp[MN];
int h[MN];
ll ans=0,ii=1,jj=1;
int main(){
scanf("%d",&n);
F(i,1,n)scanf("%d",a+i),ap[i]=i;
F(i,1,n)scanf("%d",b+i),bp[i]=i;
sort(ap+1,ap+n+1,[](int i,int j){return a[i]>a[j];});
sort(bp+1,bp+n+1,[](int i,int j){return b[i]>b[j];});
int i=1,j=1;
ll s1=0,s2=0;
while(i<=n||j<=n){
int s;
if(i<=n&&j<=n)s=s2<s1;
else s=j<=n;
if(s)s2+=b[bp[j++]];
else s1+=a[ap[i++]];
if(ans<min(s1,s2)-i-j+2)
ans=min(s1,s2)-i-j+2,ii=i,jj=j;
}printf("%lld\n",ans);
F2(i,1,ii)h[ap[i]]=1;
F(i,1,n)printf("%d ",h[i]);puts("");
F(i,1,n)h[i]=0;
F2(i,1,jj)h[bp[i]]=1;
F(i,1,n)printf("%d ",h[i]);
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/548/E
来源：牛客网
题目描述
在 Tachibana Kanade 的幻想国度中，城市的地下通道布局大致如下：城市里有 n 户人，每一户每天白天会产生一定量的废水，而这些废水都在晚上排出。第 i 户白天会产生废水 vivi。同时因为这是一个神奇的国度，所以每户在晚上有一定的废水处理能力 wiwi。
有 m 条连接户与户之间的下水道，第 i 条下水道可以双向连通，连接了第 aiai 户和第 bibi 户，但是由于该国的地势十分平坦，所以水流过下水道是需要时间的，水完全流过第 i 条下水道所需要的时间为 costicosti。
现在*需要从一开始就确定所有水的流向（可以只流走一部分），以保证所有的废水都能被处理。所有的废水都被处理的定义是：设第 i 户人家最终拥有的废水为 v′ivi′，则对于所有户，都有 v′i≤wivi′≤wi。
等到*确定完水的流向方案后，所有水都会开始流动，现在*希望在 L 时间内让所有水都被处理，请告诉她 L 的最小可能长度是多少。如果不存在解，请输出 -1。
输入描述:
输入的第一行为两个正整数 n,m。
接下来有 n 行，每行两个整数 vi,wivi,wi。
接下来有 m 行，每行三个整数 ai,bi,costiai,bi,costi。
以上各值的意义如「题目描述」所示。
输出描述:
输出一个整数，表示最小值，如果不可能就输出-1。示例1
输入
复制3 2 6 2 2 4 3 7 1 2 10 2 3 20
输出
复制20
说明
我们安排 1 点到 2 点流 4 个单位的水，2 点到3 点流2个单位的水，同时进行，显然时间为 20
备注:
n≤200,m≤500,1≤vi,wi≤1000,1≤costi≤109
作者：RainAir
链接：https://ac.nowcoder.com/discuss/173818
来源：牛客网
E.Dream City不会1啊
简单的网络流题。
抛开要求时间的限制，我们直接考虑如何判断这些废水是否可以被处理。我们把每户人家看做一个点，发现限制主要是在点而不是在边，我们就可以很自然地将每个点 vv 拆成两个点 v1v1 和 v2v2 ，建立源点 SS 和汇点 TT，对于每一个 vv，我们建立源点到 v1v1 的弧，容量为该点一开始拥有废水的数量 vivi，v2v2 连向 TT 一条容量为废水处理数量 wiwi 的弧。对于原图的每一条边 (a,b)(a,b)，连接 a1a1 和 b2b2 一条容量为无限大的弧。 该网络的最大流等价于最大能处理的废水数量。
现在我们要求能处理前提下的最短时间，发现是让所有安排方案中花费时间最大的方案花费时间最小，我们发现「最大的时间花费最小」是一个经典的带有单调性的问题。首先跑 FloydFloyd 确定任意两点间的最短路径，二分最大值 LL 后直接对于每对最短距离 ≤L≤L 的点对直接建立上述的边就可以了。
#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=410;
const int MM=40605;
const int inf=0x3f3f3f3f;
int n,m,v[MN],w[MN],tot1=0,tot2=0,mx=0;
struct data{int a,b,c;}es[505];
int to[MM],nxt[MM],c[MM],h[MN],cnt;
inline void ins(int s,int t,int w){
to[cnt]=t;nxt[cnt]=h[s];c[cnt]=w;h[s]=cnt++;
to[cnt]=s;nxt[cnt]=h[t];c[cnt]=0;h[t]=cnt++;
}
int S,T,iter[MN],level[MN],gap[MN],que[MN];
inline void bfs(){
memset(level,-1,sizeof(level));
memset(gap,0,sizeof(gap));
level[T]=0;gap[0]=1;
reg int he=0,ta=1;que[he]=T;
while(he<ta){
reg int v=que[he++];
for(reg int i=h[v];~i;i=nxt[i])
if(~level[to[i]]){
level[to[i]]=level[v]+1;
gap[level[to[i]]]++;que[ta++]=to[i];
}
}
}
inline int dfs(int x,int f){
if(x==T)return f;
reg int used=0,w;
for(reg int &i=iter[x];~i;i=nxt[i])
if(c[i]&&level[to[i]]==level[x]-1){
w=dfs(to[i],min(f-used,c[i]));
used+=w;c[i]-=w;c[i^1]+=w;
if(f==used)return f;
}
if(!(--gap[level[x]]))level[S]=T+2;
iter[x]=h[x];gap[++level[x]]++;
return used;
}
inline int SAP(){
reg int res=0;bfs();
for(reg int i=1;i<=T;i++)iter[i]=h[i];
while(level[S]<T+2)res+=dfs(S,inf);
return res;
}
int f[MN][MN];
inline bool check(int x){
memset(h,-1,sizeof(h));cnt=0;
for(reg int i=1;i<=n;i++)ins(S,i,v[i]),ins(i+n,T,w[i]),ins(i,i+n,inf);
for(reg int i=1;i<=n;i++)
for(reg int j=i+1;j<=n;j++){
if(f[i][j]>x)continue;
ins(i,j+n,inf);ins(j,i+n,inf);
}
return SAP()==tot1;
}
int main(){
scanf("%d%d",&n,&m);memset(f,0x3f,sizeof(f));
for(reg int i=1;i<=n;i++)scanf("%d%d",v+i,w+i),tot1+=v[i],tot2+=w[i];
if(tot1>tot2)return 0*puts("-1");
for(reg int i=1,s,t,c;i<=m;i++)
scanf("%d%d%d",&s,&t,&c),f[s][t]=f[t][s]=min(f[s][t],c),mx=max(mx,c);
for(reg int i=1;i<=n;i++)
for(reg int j=1;j<=n;j++)
for(reg int k=1;k<=n;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
reg int l=0,r=mx,ans=-1;T=n+n+1;
while(l<=r){
reg int mid=(l+r>>1);
if(check(mid))ans=mid,r=mid-1;
else l=mid+1;
}printf("%d\n",ans);
return 0;
}
链接：https://ac.nowcoder.com/acm/contest/548/F
来源：牛客网
题目描述
立华奏是一个天天打比赛的萌新。
省选将至，萌新立华奏深知自己没有希望进入省队，因此开始颓废。她正在颓废一款名为《IODS 9102》的游戏。
在游戏中，立华奏拥有 k 点血量，而她的对手拥有 q 点血量。当她的血量变为 0 时，游戏便结束了；同理，如果对方的血量变为 0，立华奏就获胜了。在立华奏手中，有 n 种武器，编号分别为1,2,⋯,n1,2,⋯,n，每一种武器在使用后，都能让对方受到 1 点伤害，且此后不得再次使用这个武器。同时，对方拥有m−1m−1 种反击魔咒，编号分别为 2,3,4,⋯,m2,3,4,⋯,m（如果 m = 1，则可认为此时不具有反击魔咒）。如果立华奏在使用第 i 种武器攻击对方时，对方恰好有编号为 j 的魔咒，且j∣ij∣i， 那么立华奏会受到 1 点伤害（注意此时，攻击仍然是有效的，即对方的血量仍然会减少 1），同时对方也可以再次使用这个反击魔咒。
由于立华奏是个萌新，因此对方保证不会主动攻击立华奏 。
现在，立华奏想要知道，自己是否存在一种攻击方案，使得自己取得胜利。
输入描述:
输入包含多组数据。
输入的第一行包含一个整数 T，表示数据组数。
接下来 T 行，每行包含四个整数 k, q, n, m，描述一组数据。
输出描述:
输出 T 行，每行描述一组数据的解。如果本组数据中，立华奏存在必胜策略，则输出 Yes，否则输出 QAQ。示例1
你可以认为数据保证不会出现平局的情形。
输入
复制5 0 23333 2333333 5 1 1999999999 29999999999999 9 1 998244353998244 12345678 9 1 3 3 4 1 5 6 7
输出
复制QAQ Yes QAQ QAQ QAQ
说明
对于第一组样例，立华奏开始就死掉了，因此答案为QAQ
对于第二组样例，你只需要使用所有的不含{2,3,4,5,6,7,8,9}因子的武器即可，显然在 29999999999999 内存在这些武器
对于第三组样例，立华奏的武器只有12345678个，但她的对手血量更多，显然她不可能取胜
对于第四组样例，你的血量为1，代表你不能使用会触发反击魔咒的武器，答案为QAQ
对于第五组样例，与第四组样例是相同的
备注:
1⩽T⩽105,0⩽k⩽1018,0<q⩽1018,0⩽n⩽1018,1⩽m⩽20
#include<iostream>
using namespace std;
int p[]={2,3,5,7,11,13,17,19,23};
int main()
{
long t;
cin>>t;
while(t--)
{
long long k,q,n,m;
cin>>k>>q>>n>>m;
for(int i=0;p[i]<=m;i++)
n-=n/p[i];
if(k&&k+n>q)
cout<<"Yes"<<endl;
else
cout<<"QAQ"<<endl;
}
return 0;
}
作者：RainAir
链接：https://ac.nowcoder.com/discuss/173818
来源：牛客网
F.Game
简单的数学题。
首先，你需要注意到题面种“若存在 j∣ij∣i，则会使的你的血量减少 11”这句话的含义，是“如果存在，那么血量减1”，因此无论有多少个
满足 j∣ij∣i ，你的血量都只会减少 11
考虑k=0k=0时，你开局就死了，因此答案一定为QAQ
考虑k=1k=1，即你不能选择任何会触发反击魔咒的武器，即你能够选择的数，不是[2,m][2,m]中任何一个数的倍数。当 m=1m=1 时，注意到我们不需要考虑任何情形。否则，考虑任意一个数d∈[2,m]d∈[2,m]，若其不为素数，则其一定有真素因子pp，若p∤xp∤x，则d∤xd∤x，因此我们只需要考虑[2,m][2,m]的全体素数构成的集合，不妨记其为PmPm，则显然答案为：
∑ni=1∏j∈Pm[j∤i]∑i=1n∏j∈Pm[j∤i]
然而这个式子难以处理，因此我们重新考虑后面的谓词表达式。记P=∏j∈PmjP=∏j∈Pmj，那么如果∀j∈Pm∀j∈Pm，都有j∤xj∤x，那么一定有(P,x)=1(P,x)=1，反之亦然。
结论1：∀j∈Pm,都有j∤x的充要条件为(P,x)=1∀j∈Pm,都有j∤x的充要条件为(P,x)=1
证明：必要性是显然的。
充分性：假设(P,x)=d≠1(P,x)=d≠1，那么一定有d∣P,d∣xd∣P,d∣x，设P=p1p2⋯psP=p1p2⋯ps，则一定存在ii使得d=pid=pi，即pi∣xpi∣x，与条件矛盾。
因此，我们便可以计算出我们能造成的总伤害AA：
A=∑ni=1[(P,i)=1]=∑ni=1∑d∣(P,i)μ(d)=∑d∣Pμ(d)∑i∣d1=∑d∣P⌊Pd⌋μ(d)A=∑i=1n[(P,i)=1]=∑i=1n∑d∣(P,i)μ(d)=∑d∣Pμ(d)∑i∣d1=∑d∣P⌊Pd⌋μ(d)
预处理出[2,m][2,m]的μ(x)μ(x)，这个式子就可以通过枚举PP的因子计算完成。由于PP为π(m)π(m)个不同素数的乘积，因此它的因子个数为2π(m)2π(m)。时间复杂度O(T2π(m))O(T2π(m))，考虑到π(n)∼nlognπ(n)∼nlogn可以轻松通过此题
考虑k>1k>1，我们会发现，我们可以使用k−1k−1次会触发反击魔咒的武器，因此总伤害即为A′=min{A+k−1,n}A′=min{A+k−1,n}（要对 nn 取min的原因是每种武器只能用1次，最多只能造成 nn 点伤害）
最后，我们只需要判定A′⩾qA′⩾q输出Yes，否则输出No即可