首页 > 数学家的迷题
开通博客写题解
头像 FutaRian
发表于 2021-06-26 18:18:18
感觉就很生草。 提供两种解法，分别是线段树套 bitset 的 和 。 考场上开场开了 D ，第一反应就是分块套 bitset ，算了算时间复杂度肯定爆了，就弃掉了，旁边的同学打了后直接 T 掉。 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 HGDB
发表于 2021-08-26 19:30:20
题意 有个数 有两种操作 将的值改为 给定区间，求出的不同的素数因子个数 思路 这里可以用线段树维护区间区间乘积可以被哪些素数整除 首先预处理出内的所有素数，方便查找素因子 维护数组表示第个节点表示的区间乘积可以被第个素数整除 显然如果使用数组区间操作时间复杂度很高，由于这里数组只有和两种情况， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Backl1ght
发表于 2021-06-26 11:06:43
数学家的迷题 对于操作2，其答案为区间内元素不同质因数的个数。 注意到，而内的素数个数约有个。如果使用bitset存储每个元素的质因数，再用线段树维护区间内bitset或和，即可求得区间内元素不同质因数，进一步就可以获取其质因数个数。 对于一个数，可以求出其所有质因数，所以建线段树的复杂度为，单点更 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”