Codeforces CodeTON Round 3 D. Count GCD【状压、容斥原理计数】

D. Count GCD

D

题意

给定一个长度为 n n n 的正整数数组 a a a ∀ 1 ≤ i ≤ n , a i ≤ m \forall 1 \leq i \leq n,a_i \leq m ∀1inaim

先要要统计满足以下条件的数组 b b b 的数量:

  • ∀ 1 ≤ i ≤ n , b i ≤ m \forall 1 \leq i \leq n,b_i \leq m ∀1inbim
  • g c d ( b 1 , b 2 , b 3 , . . . b i ) = a i gcd(b_1,b_2,b_3,...b_i) = a_i gcd(b1,b2,b3,...bi)=ai
思路

可以发现在当前的 i i i g c d ( a 1 , a 2 , . . . a i − 1 ) = a i − 1 gcd(a_1,a_2,...a_{i -1}) = a_{i -1} gcd(a1,a2,...ai1)=ai1,那么只要 g c d ( a i − 1 , b i ) = a i gcd(a_{i - 1},b_i) = a_i gcd(ai1,bi)=ai 就可以了,那么我们可以得出结论: a i ∣ a i − 1 a_i \mid a_{i - 1} aiai1,也即是 a i − 1 a_{i - 1} ai1 a i a_i ai 的因子,同时 a i ∣ b i a_i \mid b_i aibi

这样子答案就是每个位置可选的数量累乘,问题是如何快速求出位置 i i i 可行的 b i b_i bi 数量

b i b_i bi 一定得是 a i a_i ai 的倍数,我们可以假设 k ⋅ a i = b i k \cdot a_i = b_i kai=bi,那么不同的 k k k 的数量就是 b i b_i bi 的数量
那么 g c d ( a i − 1 , b i ) = a i ⇒ g c d ( a i − 1 a i , k ) = 1 gcd(a_{i - 1}, b_i) = a_i \Rarr gcd(\dfrac{a_{i - 1}}{a_i}, k) = 1 gcd(ai1,bi)=aigcd(aiai1,k)=1,也就是 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 中出现的质因子不能在 k k k 中出现

为了快速得到 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 的所有质因子,我们发现 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 的质因子一定是 a 1 a_1 a1 的质因子。这是因为 a i ∣ a i − 1 ∣ . . . . ∣ a 2 ∣ a 1 a_i \mid a_{i - 1} \mid .... \mid a_2 \mid a_1 aiai1....a2a1;并且最小的 10 10 10 个质数相乘就已经大于 1 0 9 10^9 109 了!所以我们只需要最多 9 9 9 个不同的质数(不一定是最小的 9 9 9 个)就可以表示小于等于 1 0 9 10^9 109 的数了

我们只需要在 O ( m ) O(m) O(m) 下预处理 得出 a 1 a_1 a1质因子,然后对于每个 i > 2 i > 2 i>2,枚举 a 1 a_1 a1 的质因子,看看 a i a_i ai 是否被其整除,即可快速得出 a i a_i ai 的所有质因子,质因子数量都不超过 9 9 9 个!我们这里就可以考虑状压 + 容斥原理来计数了

容斥原理
集合 S S S 的子集 A 1 A_1 A1 具有性质 P 1 P_1 P1,子集 A 2 A_2 A2 具有性质 P 2 P_2 P2,… A n A_n An 具有性质 P n P_n Pn


(1)集合 S S S不具有性质 P 1 , P 2 , . . . , P n P_1,P_2,...,P_n P1,P2,...,Pn 的对象个数为:
∣ A 1 ‾ ∩ A 2 ‾ , . . . , ∩ A n ‾ ∣ = ∣ S ∣ − ∑ ∣ A i ∣ + ∑ ∣ A i ∩ A j ∣ − ∑ ∣ A i ∩ A j ∩ A k ∣ + . . . + ( − 1 ) n ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ | \overline{A_1} \cap \overline{A_2}, ..., \cap \overline{A_n}| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + ... + (-1)^{n} |A_1 \cap A_2 \cap ... \cap A_n| A1A2,...,An=SAi+AiAjAiAjAk+...+(1)nA1A2...An


(2)集合 S S S至少具有性质 P 1 , P 2 , . . . P n P_1,P_2,...P_n P1,P2,...Pn 之一的对象个数为:
∣ A 1 ∪ A 2 , . . . , ∪ A n ∣ = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ∑ ∣ A i ∩ A j ∩ A k ∣ + . . . + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ | A_1 \cup A_2, ..., \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| + ... + (-1)^{n + 1} |A_1 \cap A_2 \cap ... \cap A_n| A1A2,...,An=AiAiAj+AiAjAk+...+(1)n+1A1A2...An

因为性质很少,最多只有 9 9 9 个(分别被不同的 9 9 9 个质数整除),我们要求出与 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 互质的 k k k 的数量,也就是 k k k 不能拥有 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 的质因子,也就是 k k k 不具有性质 P 1 , P 2 , . . . P k P_1,P_2,...P_k P1,P2,...Pk k k k a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 质因子数),只需要用容斥原理简单地通过整除得到即可,注意 k ≤ m a i k \leq \dfrac{m}{a_i} kaim

时间复杂度: O ( m + 9 ⋅ 2 9 ⋅ log ⁡ m ) O(\sqrt m + 9 \cdot 2^9 \cdot \log m) O(m +929logm)

最后那个 log ⁡ m \log m logm 是因为: a 1 a_1 a1 的每个质因子数量一定非递减,如果某个质因子在 a i − 1 a i \dfrac{a_{i - 1}}{a_i} aiai1 中出现,说明这个质因子数量在这里至少 − 1 -1 1 了,那么从 a 1 a_1 a1 减少到 a n a_n an,质因子最多就 log ⁡ m \log m logm 个,很快就没了

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;const int INF=0x3f3f3f3f;
const long long INFLL=1e18;typedef long long ll;template<class T>
constexpr T power(T a, ll b){T res = 1;while(b){if(b&1) res = res * a;a = a * a;b >>= 1;}return res;
}constexpr ll mul(ll a,ll b,ll mod){ //快速乘,避免两个long long相乘取模溢出ll res = a * b - ll(1.L * a * b / mod) * mod;res %= mod;if(res < 0) res += mod; //误差return res;
}template<ll P>
struct MLL{ll x;constexpr MLL() = default;constexpr MLL(ll x) : x(norm(x % getMod())) {}static ll Mod;constexpr static ll getMod(){if(P > 0) return P;return Mod;}constexpr static void setMod(int _Mod){Mod = _Mod;}constexpr ll norm(ll x) const{if(x < 0){x += getMod();}if(x >= getMod()){x -= getMod();}return x;}constexpr ll val() const{return x;}explicit constexpr operator ll() const{ return x; //将结构体显示转换为ll类型: ll res = static_cast<ll>(OBJ)}constexpr MLL operator -() const{ //负号,等价于加上ModMLL res;res.x = norm(getMod() - x);return res;}constexpr MLL inv() const{assert(x != 0);return power(*this, getMod() - 2); //用费马小定理求逆}constexpr MLL& operator *= (MLL rhs) & { //& 表示“this”指针不能指向一个临时对象或const对象x = mul(x, rhs.x, getMod()); //该函数只能被一个左值调用return *this;}constexpr MLL& operator += (MLL rhs) & {x = norm(x + rhs.x);return *this;}constexpr MLL& operator -= (MLL rhs) & {x = norm(x - rhs.x);return *this;}constexpr MLL& operator /= (MLL rhs) & {return *this *= rhs.inv();}friend constexpr MLL operator * (MLL lhs, MLL rhs){MLL res = lhs;res *= rhs;return res;}friend constexpr MLL operator + (MLL lhs, MLL rhs){MLL res = lhs;res += rhs;return res;}friend constexpr MLL operator - (MLL lhs, MLL rhs){MLL res = lhs;res -= rhs;return res;}friend constexpr MLL operator / (MLL lhs, MLL rhs){MLL res = lhs;res /= rhs;return res;}friend constexpr std::istream& operator >> (std::istream& is, MLL& a){ll v;is >> v;a = MLL(v);return is;}friend constexpr std::ostream& operator << (std::ostream& os, MLL& a){return os << a.val();}friend constexpr bool operator == (MLL lhs, MLL rhs){return lhs.val() == rhs.val();}friend constexpr bool operator != (MLL lhs, MLL rhs){return lhs.val() != rhs.val();}
};const ll mod = 998244353;
using Z = MLL<mod>;std::vector<int> get_d(int x){std::vector<int> d;for(int i = 2; i * i <= x; ++i){if(x % i ) continue;d.push_back(i);while(x % i == 0) x /= i;}if(x > 1) d.push_back(x);return d;
}void solve(){int n, m;std::cin >> n >> m;std::vector<int> a(n + 1);fore(i, 1, n + 1) std::cin >> a[i];fore(i, 2, n + 1)if(a[i - 1] % a[i]){std::cout << "0\n";return;}auto div = get_d(a[1]);Z ans = 1;fore(i, 2, n + 1){int val = a[i - 1] / a[i];std::vector<int> left;for(auto d : div)if(val % d == 0)left.push_back(d);int sz = left.size();ll K = m / a[i]; //k的上界ll tot = K;fore(mask, 1, 1 << sz){int cnt = __builtin_popcount(mask); //容斥原理系数int now = 1;fore(j, 0, sz)if(mask >> j & 1)now *= left[j];if(cnt & 1) tot -= K / now;else tot += K / now;}ans *= tot;}std::cout << ans << endl;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;std::cin >> t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/298139.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Oracle】oracle、mysql、sql server三者区别

欢迎来到《小5讲堂》&#xff0c;大家好&#xff0c;我是全栈小5。 这是《Oracle》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识…

Python学习: 错误和异常

Python 语法错误 解析错误(Parsing Error)通常指的是程序无法正确地解析(识别、分析)所给定的代码,通常是由于代码中存在语法错误或者其他无法理解的结构导致的。这可能是由于缺少括号、缩进错误、未关闭的引号或其他括号等问题造成的。 语法错误(Syntax Error)是指程序…

【APUE】网络socket编程温度采集智能存储与上报项目技术------多进程编程

作者简介&#xff1a; 一个平凡而乐于分享的小比特&#xff0c;中南民族大学通信工程专业研究生在读&#xff0c;研究方向无线联邦学习 擅长领域&#xff1a;驱动开发&#xff0c;嵌入式软件开发&#xff0c;BSP开发 作者主页&#xff1a;一个平凡而乐于分享的小比特的个人主页…

《数据结构学习笔记---第九篇》---循环队列的实现

文章目录 1.循环队列的定义 2.循环队列的判空判满 3.创建队列并初始化 4.入队和出队 5. 返回队尾队首元素 6.释放循环队列 1.循环队列的定义 定义&#xff1a;存储队列元素的表从逻辑上被视为一个环。 我们此次实现的循环队列&#xff0c;采用顺序表 typedef struct {int…

9、逆序对的数量(含源码)

逆序对的数量 难度&#xff1a;简单 题目描述 给定一个长度为n的整数数列&#xff0c;请你计算数列中的逆序对的数量。 逆序对的定义如下&#xff1a;对于数列的第 i 个和第 j 个元素&#xff0c;如果满足 i < j 且 a[i] > a[j]&#xff0c;则其为一个逆序对&#xf…

Open3D(C++) 基于三维激光扫描点云的树冠体积计算方法

目录 一、算法原理1、原理概述2、参考文献二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 1、原理概述 针对树冠形状不规则,树冠体积难以测量和计算的问题,提出一种基于三…

Html提高——视频标签音频标签及其相关属性

HTML5 在不使用插件的情况下&#xff0c;也可以原生的支持音视频格式文件的播放&#xff0c;当然&#xff0c;支持的格式是有限的。 1、video标签 1.1、video标签的语法 <video src"文件地址" controls"controls"></video> video标签的内部…

7.java openCV4.x 入门-Mat之转换、重塑与计算

专栏简介 &#x1f492;个人主页 &#x1f4f0;专栏目录 点击上方查看更多内容 &#x1f4d6;心灵鸡汤&#x1f4d6;我们唯一拥有的就是今天&#xff0c;唯一能把握的也是今天建议把本文当作笔记来看&#xff0c;据说专栏目录里面有相应视频&#x1f92b; &#x1f9ed;文…

全国土壤类型分布数据/土壤有机质/土壤含水量分布/土壤温度/土壤质地/土壤PH

数据下载链接&#xff1a;数据下载链接 引言 土壤是指地球表面的一层疏松的物质&#xff0c;由各种颗粒状矿物质、有机物质、水分、空气、微生物等组成&#xff0c; 能生长植物。土壤是一个国家最重要的自然资源&#xff0c;它是农业发展的物质基础。我国幅员辽阔&#xff0c;自…

SD-WAN组网面临的安全挑战?如何提供有效的安全措施

SD-WAN&#xff08;软件定义广域网&#xff09;技术的广泛应用&#xff0c;企业面临着越来越多的网络安全挑战。尽管SD-WAN带来了灵活性和效率的提升&#xff0c;但其开放性和基于云的特性也带来了一系列安全威胁。本文将探讨SD-WAN组网面临的安全挑战&#xff0c;并提供一些有…

0201基础集成与使用-微信支付-支付模块-项目实战

文章目录 一、前言二、springboot集成2.1 配置信息与配置类2.2 微信相关枚举信息2.3 工具类2.4 业务接口 三、演示-支付与退款结语 一、前言 下面我以微信支付v3为例&#xff0c;通过spirngboot集成到我们的项目中&#xff0c;不依赖其他第三方框架。当然适用简单项目&#xf…

Linux多进程通信(4)——消息队列从入门到实战!

Linux多进程通信总结——进程间通信看这一篇足够啦&#xff01; 1.基本介绍 1&#xff09;消息队列的本质其实是一个内核提供的链表&#xff0c;内核基于这个链表&#xff0c;实现了一个数据结构&#xff0c;向消息队列中写数据&#xff0c;实际上是向这个数据结构中插入一个…

Vue项目登录页实现获取短信验证码的功能

之前我们写过不需要调后端接口就获取验证码的方法,具体看《无需后端接口,用原生js轻松实现验证码》这个文章。现在我们管理后台有个需求,就是登录页面需要获取验证码,用户可以输入验证码后进行登录。效果如下,当我点击获取验证码后能获取短信验证码: 这里在用户点击获取…

win11安装WSL UbuntuTLS

win11安装WSL WSL 简介WSL 1 VS WSL 2先决要求安装方法一键安装通过「控制面板」安装 WSL 基本命令Linux发行版安装Ubuntu初始化相关设置root用户密码网络工具安装安装1panel面板指导 WSl可视化工具问题总结WSL更新命令错误Ubuntu 启动初始化错误未解决问题 WSL 简介 Windows …

Sybase ASE中的char(N)的坑以及与PostgreSQL的对比

1背景 昨天,一朋友向我咨询Sybase ASE中定长字符串类型的行为,说他们的客户反映,同样的char类型的数据,通过jdbc来查,Sybase库不会带空格,而PostgreSQL会带。是不是这样的?他是PostgreSQL的专业大拿,但因为他手头没有现成的Sybase ASE环境,刚好我手上有,便于一试。 …

hive 慢sql 查询

hive 慢sql 查询 查找 hive 执行日志存储路径&#xff08;一般是 hive-audit.log &#xff09; 比如&#xff1a;/var/log/Bigdata/audit/hive/hiveserver/hive-audit.log 解析日志 获取 执行时间 执行 OperationId 执行人 UserNameroot 执行sql 数据分隔符为 \001 并写入 hiv…

vuepress-theme-hope 添加谷歌统计代码

最近做了个网站,从 cloudflare 来看访问量,过去 30 天访问量竟然有 1.32k 给我整懵逼了,我寻思不应该呀,毕竟这个网站内容还在慢慢补充中,也没告诉别人,怎么就这么多访问?搜索了下, cloudflare 还会把爬虫的请求也就算进来,所以数据相对来说就不是很准确 想到了把 Google An…

如何同时安全高效管理多个谷歌账号?

您的业务活动需要多个 Gmail 帐户吗&#xff1f;出海畅游&#xff0c;Gmail账号是少不了的工具之一&#xff0c;可以关联到Twitter、Facebook、Youtube、Chatgpt等等平台&#xff0c;可以说是海外网络的“万能锁”。但是大家都知道&#xff0c;以上这些平台注册多账号如果产生关…

Cisco交换机安全配置

Cisco交换机安全配置 前提 我们以下命令一般都要先进入Config模式 S1> enable S1# conf t S1(config)#端口安全保护 禁用未使用的端口 以关闭fa0/1到fa0/24的端口为例 S1(config)# interface range fa0/1-24 S1(config-if-range)# shutdown缓解MAC地址表攻击 防止CAM…

蓝桥杯刷题第六天(昨天忘记发了)

今天想从不一样的角度来解题&#xff1a;从时间紧张暴力求解到思路阔达直接通过所有案例 暴力方法&#xff1a; 思路第一眼看到这个问题我就想到了第一个思路就是先用两个数组一个存石子数一个存颜色状态&#xff0c;每次遍历一遍看看有没有相邻石子颜色一样且为和最小的。 im…