博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2017 Multi-University Training Contest - Team 2 TrickGCD(组合数学)
阅读量:6416 次
发布时间:2019-06-23

本文共 1529 字,大约阅读时间需要 5 分钟。

题目大意:

给你一个序列An,然后求有多少个序列Bn

满足Bi<=Ai,且这个序列的gcd不为1

 

题解:

考虑这样做

枚举一个因子k,然后求出有多少个序列的gcd包含这个因子k

然后把结果容斥一下,我们会发现,这个容斥恰好就是求莫比乌斯函数

所以直接先预处理出来即可

于是k从2到n依次枚举,然后把结果乘以u(k)加到最后的答案里。

 

另一个问题是,如何快速求出有多少个序列呢,如果单纯的把每个数除以k然后加起来,就是n^2logn

显然会超时。

所以这里先把数存起来,然后整体来做

对于k来说,每次就枚举k,2k,3k.....m*k,然后可以得到,能包含k的数有多少个,2k的数有多少个,那么我们就可以在n/k的复杂度下统计出来有多少个序列

然后枚举k,最后就是n+n/2+...n/k = nlogn的复杂度了

(可能有更好的做法)

 

#include 
#include
#include
#include
using namespace std;const int maxn = 1e5 + 100;const int MOD = 1000000007;typedef long long LL;LL minpri[maxn], H[maxn], a[maxn], ans[maxn], flag[maxn];vector
prime;const int maxlen=maxn;int mu[maxlen],prinum[maxlen], len=0;void CalPri(){ int num[maxlen]; for(int i=2;i
>= 1){ if(b&1) (ANS *= a) %= MOD; (a *= a) %= MOD; } return ANS;}int main(){ int T, n; cin>>T; Calmu(); for(int ncase = 1; ncase <= T; ncase++){ scanf("%d", &n); memset(H, 0, sizeof(H)); memset(ans, 0, sizeof(ans)); LL ANS = 0, Max = 0, Min = 1e9; for(int i = 1; i <= n; i++) scanf("%d", &a[i]), H[a[i]]++, Max = max(Max, a[i]), Min = min(Min, a[i]); for(int i = Max; i >= 0; i--) H[i] += H[i+1]; //for(int i = 1; i <= Max; i++) cout<
<<" "; cout<
0 ? 1 : 0; for(int i = 2; i <= tot; i++) (temp *= mypow(i, ans[i])) %= MOD; (ANS += temp*(-mu[x])) %= MOD; for(int i = 1; i <= tot; i++) ans[i] = 0; } (ANS += MOD) %= MOD; cout<<"Case #"<
<<": "<
<

 

转载于:https://www.cnblogs.com/Saurus/p/7246297.html

你可能感兴趣的文章
java 编译100个范例
查看>>
Session Cookie ServletContext
查看>>
单点登录SSO
查看>>
遇见有的软件开启后画面模糊怎么解决
查看>>
好系统重装助手教你怎么识别固态硬盘还是机械硬盘
查看>>
170. js中获取随机数 (记录一下)
查看>>
深入浅出爬虫之道: Python、Golang与GraphQuery的对比
查看>>
DHCP配置
查看>>
MySQL性能测试(二)——Ubuntu 14.4.02, MySQL 5.6.25, sysbench 4.8
查看>>
我的友情链接
查看>>
网络安全十大注意
查看>>
cisco虚拟局域网VLAN路由----待补充
查看>>
join命令实现文件内容拼接
查看>>
-bash:wget command not found的解决方法
查看>>
yara规则
查看>>
我的个人简历
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
KVM组件bug报告方法
查看>>
HTML5初学---坦克大战基础
查看>>