【欧拉函数】 P2568 GCD P2398 GCD SUM

太过爱你忘了你带给我的痛 2024-03-29 14:35 119阅读 0赞

[P2568 GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2568 GCD - _ _ _ _luogu.com.cn]

题意：

![dc84d6858b06ccfc4689b217939eda3d.png][]

思路：

枚举x和y一定超时，我们去枚举素数

然后就是欧拉函数典中典的套路了

![d9740627d1a3e5b7ceccdbaaf11a3604.png][]

另外一题也是一样的道理

[P2398 GCD SUM - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2398 GCD SUM - _ _ _ _luogu.com.cn]

题意：

![3e2e11f1d8ca54dbcc1b6c5cc6240e1b.png][]

![5c339e8b800f29a9864fdde3092360c0.png][]

[P2568 GCD - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2568
[dc84d6858b06ccfc4689b217939eda3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/3d2fc78d0233492183e466bcf1271bdc.png
[d9740627d1a3e5b7ceccdbaaf11a3604.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7cf7f3677c754fc7892ddbe0def2f0da.png
[P2398 GCD SUM - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P2398
[3e2e11f1d8ca54dbcc1b6c5cc6240e1b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/c01f18748d4148bf8e3657d2c272e676.png
[5c339e8b800f29a9864fdde3092360c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/75d318ab3d65421781e78b470b87834e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关 O - GCD - Extreme (II)————欧拉函数+数论基本定理

题目要求： [链接][Link 1] ![在这里插入图片描述][20190908174415651.png] 题目给你一个N，让你求如图这个G。其实...

Love The Way You Lie/ 2024年04月18日 15:08/ 0 赞/ 123 阅读

相关【欧拉函数】 P2568 GCD P2398 GCD SUM

[P2568 GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P2568 GCD - _ _ _ _luogu.com.cn] 题意： ![dc

太过爱你忘了你带给我的痛/ 2024年03月29日 14:35/ 0 赞/ 120 阅读

相关 HDU 1695-GCD（容斥原理+欧拉函数）

GCD Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

男娘i/ 2022年09月25日 02:26/ 0 赞/ 38 阅读

相关欧几里得gcd/extend_gcd

正式叙述前还写了一点自己的小感受。问题：求两个[正整数][Link 1]a，b的[最大公约数][Link 2]。大神看来是很简单的问题，但是对于去年夏天刚学python

分手后的思念是犯贱/ 2022年05月16日 02:59/ 0 赞/ 215 阅读

相关【题解】P2568 GCD

\\(Description:\\) > 求x,y小于n中gcd(x,y)为质数的对数 \\(Sample\\) \\(Input:\\) > 4 \\(Sample\

矫情吗；*/ 2022年01月12日 03:09/ 0 赞/ 298 阅读

相关 P2568 GCD

[传送门][Link 1] 设 $f\[x\]=\\sum\_i^N\\sum\_j^N\[gcd(i,j)==x\]$ 那么答案就是 $Ans=\\sum\_\{prim

骑猪看日落/ 2021年12月10日 02:53/ 0 赞/ 274 阅读

相关洛谷P2257 YY的GCD

莫比乌斯反演还是把gcd换成莫比乌斯函数，在最外层枚举素数p，对于每个素数p，gcd莫比乌斯反演 include <bits/stdc++.h> de

忘是亡心i/ 2021年11月08日 17:26/ 0 赞/ 283 阅读

相关题解洛谷P2568 GCD

\\(update\\ \\ \\ 2018/11/18\\)修改了\\(Letex\\)，其他没有变中间我\\(AFO\\)了,成功从红名掉到了蓝名 \\(update

约定不等于承诺〃/ 2021年10月26日 21:20/ 0 赞/ 495 阅读

相关【题解】Luogu P2257 YY的GCD

[原题传送门][Link 1] 这题需要运用[莫比乌斯反演(懵逼钨丝繁衍)][Link 2] 显然题目的答案就是\\\[ Ans=\\sum\_\{i=1\}^N

た入场券/ 2021年10月01日 06:44/ 0 赞/ 358 阅读

相关 HDU - 1787 - GCD Again 【欧拉函数】题解

目录 1.题目 2.代码 1.题目 Do you have spent some time to think

超、凢脫俗/ 2021年07月24日 12:59/ 0 赞/ 415 阅读