首页 > 代码库 > bzoj2818gcd
bzoj2818gcd
原理很简单
题解我就不自己写了……
做这题的时候，懂得了一个非常重要的转化：求(x, y) = k, 1 <= x, y <= n的对数等于求(x, y) = 1, 1 <= x, y <= n/k的对数！所以，枚举每个质数p（线性筛素数的方法见：线性时间内筛素数和欧拉函数），然后求(x, y) = 1, 1 <= x, y <= n/p的个数。
那(x, y) = 1的个数如何求呢？其实就是求互质的数的个数。在[1, y]和y互质的数有phi(y)个，如果我们令x < y，那么答案就是sigma(phi(y))。因为x, y是等价的，所以答案*2，又因为(1, 1)只有一对，所以-1。最终答案为sigma(sigma(phi(n/prime[i])) * 2 - 1)。
提交的时候我都快疯了
在这个题中，我们应该需要注意两点：
一、bzoj上215错误会被报为wa，坑爹啊
二、在数组开的很大的情况下，能不用int64的就不用
因为内存占用过大会大致速度变慢
代码：
1 var i,n,tot:longint; 2 ans:int64; 3 phi:array[0..10000000] of int64; 4 p:array[0..10000000] of longint; 5 procedure get; 6 var i,j:longint; 7 begin 8 fillchar(phi,sizeof(phi),0); 9 tot:=0;10 phi[1]:=0;11 for i:=2 to n do12 if phi[i]=0 then13 begin14 phi[i]:=i-1;inc(tot);p[tot]:=i;15 j:=i+i;16 while j<=n do17 begin18 if phi[j]=0 then phi[j]:=j;19 phi[j]:=(phi[j] div i)*(i-1);20 inc(j,i);21 end;22 end;23 end;24 procedure main;25 begin26 readln(n);27 get;28 for i:=2 to n do inc(phi[i],phi[i-1]);29 ans:=0;30 for i:=1 to tot do inc(ans,2*phi[n div p[i]]+1);31 writeln(ans);32 end;33 begin34 main;35 end.36
（我习惯把phi[1]定为0，因为这比较符合逻辑。）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。