当前位置: 首页 > news >正文

CF1016G Appropriate Team

首先一个结论是:只有在 \(Y \bmod X =0\) 时,才有答案。

证明显然,因为 \(\gcd\)\(\operatorname{lcm}\) 的性质,\(a_i\)\(v\)\(X\) 的倍数,\(a_j\)\(v\)\(Y\) 的因数。

那么接下来,因为 \(X\)\(Y\) 是固定的,容易想到将它们分解质因数。

分解质因数你可以使用 Pollard's Rho 算法,但其实有个更简单的做法,我们待会儿介绍。

现在设 \(X=p_1^{cntx_1}p_2^{cntx_2}...p_k^{cntx_k}\)\(Y=p_1^{cnty_1}p_2^{cnty_2}...p_k^{cnty_k}\),把质因数集合定为 \(Y\) 的质因数集合,如果 \(X\) 没有某个质因数 \(p_i\)\(cntx_i=0\)

接着把所有 \(a_i\)\(v\) 也分解成这个形式,\(a_i=p_1^{cnt_{i,1}}p_2^{cnt_{i,2}}...p_k^{cnt_{i,k}}\)\(v=p_1^{cntv_1}p_2^{cntv_2}...p_k^{cntv_k}\)

那么 \(\gcd\)\(\operatorname{lcm}\) 的限制就可以转化为,对于 \(1\le s\le k\)\(\min(cnt_{i,s},cntv_s)=cntx_s\)\(\max(cnt_{j,s},cntv_s)=cnty_s\)

如果 \(cntx_s=cnty_s\) 的话,显然 \(v\) 必须恰好有 \(cntx_s\)\(p_s\),因为 \(a_i\)\(X\) 的倍数,\(a_j\)\(Y\) 的因数,所以 \(cnt_{i,s}\ge cntx_s\)\(cnt_{j,s}\le cnty_s\),那么一定能够满足限制,所以可以无视这一位,把它删掉了。

如果 \(cntx_s < cnty_s\) 的话,我们分类讨论,发现只有一种情况是不合法的:\(cnt_{i,s}> cntx_s\)\(cnt_{j,s}< cnty_s\),这时候 \(cntv_s\) 既要等于 \(cntx_s\),又要等于 \(cnty_s\),于是就矛盾了。

这时候问题可以转到我们熟悉的二进制上去!设 \(minn_x\) 表示所有是 \(X\) 倍数的 \(a_i\) 对于每个 \(s\),若 \(cnt_{i,s}> cntx_s\) 则第 \(s\) 位为 \(1\),否则为 \(0\),最后的二进制总和为 \(x\) 的有几个。类似地,设 \(maxn_x\) 表示所有是 \(Y\) 因数的 \(a_i\) 对于每个 \(s\),若 \(cnt_{i,s}< cnty_s\) 则第 \(s\) 位为 \(1\),否则为 \(0\),最后的二进制总和为 \(x\) 的有几个。

于是最后的答案就为 \(\sum minn_imaxn_j \,[\,i\&j =0\,]\)

最后就是,怎么对 \(Y\) 分解质因数。题解给出了一个非常巧妙的做法:先把 \(1\sim 10^6\) 的质数筛出来,把 \(Y\) 在这之间的质因数去掉。那么剩下的数 \(s\) 要么是一个大质数,要么是一个大质数的平方,要么是两个不同的大质数的乘积。是不是一个大质数的平方很容易用 \(\operatorname{sqrtl}\) 判断。接下来,判断 \(s\) 是否等于 \(p\times q\),你发现如果不存在一个 \(a_i\)\(p\) 的倍数但不是 \(q\) 的倍数或是 \(q\) 的倍数但不是 \(p\) 的倍数,那么所有的 \(a_i\) 要么都没有 \(p\)\(q\) 两个因子,要么都有这两个因子,那么我们可以把 \(p\times q\) 看成一个因子,这对答案不会有影响。所以判断 \(s\) 是否等于 \(p\times q\),只要将 \(s\) 和所有 \(a_i\) 取个 \(\gcd\),若 \(\gcd\) 不等于 \(1\) 也不等于 \(s\),说明找到了 \(p\)\(q\) 中的一个,就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=1e6+10;
int n,m,x,y,s,ans,a[N],minn[(1<<15)+10],maxn[(1<<15)+10];
int tot,vis[M],pr[M],p[16],cntx[16],cnty[16];
void find()
{for(int i=1,g;i<=n;i++){g=__gcd(a[i],s);if(g!=1&&g!=s){p[++m]=g,cnty[m]=1;p[++m]=s/g,cnty[m]=1;return;}}p[++m]=s,cnty[m]=1;return;
}
signed main()
{for(int i=2;i<=M-10;i++){if(!vis[i])pr[++tot]=i;for(int j=1;j<=tot&&pr[j]*i<=M-10;j++){vis[pr[j]*i]=1;if(i%pr[j]==0)break;}}scanf("%lld%lld%lld",&n,&x,&y),s=y;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);if(y%x)printf("0");else{for(int i=1;i<=tot;i++){if(s%pr[i]==0){p[++m]=pr[i];while(s%pr[i]==0)s/=pr[i],cnty[m]++;}}if(s>1){int sq=sqrtl(s);if(sq*sq==s)p[++m]=sq,cnty[m]=2;else find();}for(int i=1,s=x,j=0;i<=m;i++){while(s%p[i]==0)cntx[i]++,s/=p[i];if(cntx[i]!=cnty[i])p[++j]=p[i],cntx[j]=cntx[i],cnty[j]=cnty[i];if(i==m)m=j;}for(int i=1,sum;i<=n;i++){if(a[i]%x)continue;sum=0;for(int j=1,s=a[i],cnt;j<=m;j++){cnt=0;while(s%p[j]==0)cnt++,s/=p[j];if(cnt>cntx[j])sum+=(1<<(j-1));}minn[sum]++;}for(int i=1,sum;i<=n;i++){if(y%a[i])continue;sum=0;for(int j=1,s=a[i],cnt;j<=m;j++){cnt=0;while(s%p[j]==0)cnt++,s/=p[j];if(cnt<cnty[j])sum+=(1<<(j-1));}maxn[sum]++;}for(int i=0;i<m;i++)for(int j=0;j<(1<<m);j++)if((j>>i)&1)maxn[j]+=maxn[j-(1<<i)];for(int i=0;i<(1<<m);i++)ans+=minn[i]*maxn[(1<<m)-1-i];printf("%lld\n",ans);}return 0;
}
http://www.hskmm.com/?act=detail&tid=12480

相关文章:

  • CF494C Helping People
  • 深入解析:Extract Chart Data Directly to Excel
  • AOSP Android12 Source 下载同步
  • 02020404 EF Core基础04-自增主键、Guid主键、混合自增、Hi/Lo算法、Migration深入、数据库其它迁移命令
  • 02020403 EF Core基础03-Fluent API、Data Annotation、两种配置的选择
  • Java中异步任务的执行方式有几种?
  • 广二联考题解补全计划:
  • Chapter 8 Contour / Shape Detection
  • 【左程云算法笔记016】双端队列-双链表和固定数组实现 - 教程
  • java相关问题:面向对象入门2与类的识别
  • EXCEL自动调整列宽的快捷键
  • 【C++实战⑬】解锁C++文件操作:从基础到实战的进阶之路 - 实践
  • 破解塔吊顶升高危难题!让事故率降 50%、审批快 70%
  • logicFlow________文档2
  • CF2086D Even String
  • logicflow___文档3
  • 2025年运营商API安全建设最佳实践:某头部省级电信案例解析与方案推荐
  • 软件工程第二次作业-第一次个人编程作业
  • 面向对象入门2与类的识别
  • 202508_天山固网_to
  • jmeter分布式压测
  • 怎么屏蔽 ahref.com 上你不想看到的网站链接(垃圾外链)
  • 浅谈字典树
  • go-mapus为局域网地图协作而生
  • 《手搓动态顺序表:从数组到自动扩容的华丽转身》 - 详解
  • 板子大全
  • 通过人大金仓数据库的逻辑备份与还原功能实现数据迁移
  • 第十二节:订单普通下单、支付回调、退款、退款回调详解
  • 《原子习惯》-读书笔记7
  • 第3周预习作业