首页 > List Of Integers
开通博客写题解
头像 shyyhs
发表于 2020-09-25 11:23:16
首先我们都会求[1,n]与给定的p互质的个数对吧?用容斥原理,拿n-1个p的质因子+2个p的质因子...这样容斥下去即可.题目是要求大于x第k个与p互质的数.很明显是有单调性的,我们来二分n然后ck一下,假定cnt[n]表示[1,n]与给定的p互质的个数,那么我们是要求大于x的第k个,那么我们直接拿 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-25 07:58:18
List of Intergers 题目大意 求第大的大于等于 且与 互质的数 分析 即，求最小的 使： 莫比乌斯反演 那么看见这个形式，自然而然地会想到这个东西： 所以就可以把 写成： 那么交求和顺序，先枚举 的因子 ，可以得到: 那么，这个时候，后面这一块，已经是十分好求的了，可以直接 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 嘻嘻嘻嘻嘻嘻嘻
发表于 2020-09-24 17:47:31
题目：https://ac.nowcoder.com/acm/problem/112558题意：t次询问[x,p,k]，找出比x大且与p互质的第k个数分析： 假设答案为ans，那么就是求[x+1,ans]之间恰好有k个数与p互质，同时ans刚好要与p互质； 范围为1e6，同时随着ans的增大与p互 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 萝卜朝天椒
发表于 2020-09-24 21:01:21
题意：询问[x,p,k]，找出比x大且与p互质的第k个数 解题思路： idea很简单 首先容斥原理可以算出某个范围内的与x互质的个数（oi-wiki上有介绍） https://oi-wiki.org/math/inclusion-exclusion- 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-25 08:17:09
分析 我们考虑弱化版本：对于求一定范围内与互质的数个数那么就是 所以答案就是枚举所有的质因子，进行简单容斥即可所以我们需要知道容斥系数这里我们就可以利用莫比乌斯函数的另一种用途了：作为质因子的容斥系数因为莫比乌斯函数满足 所以我们直接线性筛所有的莫比乌斯函数再二分答案判断即可时间复杂度： 代码 // 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 __故人__
发表于 2020-09-25 08:59:23
分析 求第 大的大于等于 且与 互质的数，那么我们先考虑如果我们枚举第 大是谁，其实并不好做。这样时间复杂度的的下限至少为 。那么我们考虑二分一个值 ， 与 互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于 这个条件，做一次差分就好了。那么现在算法的主要问 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-09-25 21:33:41
题意：给你x、p、k三个数，让你求大于x的第k个与p互素的数？ 思路：求出p的质因子，然后求小于等于x的与p互质的个数求出为j，题意就相当于求大于0的第k+j个与p互素的数了，二分枚举答案，求小于等于某一个数与p互质的个数使用容斥原理计算得出。 代码： #include<cstdio> 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2020-09-25 11:02:45
做法：二分+容斥 思路： 1.先考虑 这个问题,想到莫比乌斯函数的性质想到容斥原理 2.先用莫比乌斯函数线性筛把莫比乌斯函数求出来 3.进行利用容斥原理二分代码 #include <bits/stdc++.h> using namespace std; #define pb pus 展开全文
去ta的博客 赞 (1) 回复(1) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”