BZOJ 2818——Gcd

喜欢ヅ旅行 2022-07-24 08:09 29阅读 0赞

题意：给定n，求gcd（x,y)==p 的对数，其中（1<=x<y<n)

思路：

求`(x, y) = k, 1 <= x, y <= n`的对数等于求`(x, y) = 1, 1 <= x, y <= n/k`的对数！所以，枚举每个质数`p`（线性筛素数的方法见：[线性时间内筛素数和欧拉函数][Link 1]），然后求`(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)`。

参考：https://oi.abcdabcd987.com/eight-gcd-problems/

code：

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <set>
    #include <cmath>
    #include <vector>
    using namespace std;
    using namespace std;
    typedef long long ll;
    const int N = 10000005;
    const ll maxn=1e18+100;
    int n,len;
    int p[N],phi[N];
    bool vis[N];
    
    int main()
    {
    	scanf("%d",&n);
    	len=0;
    	for (int i=2;i<=n;i++){
    		if (!vis[i]){
    			p[len++]=i;
    			phi[i]=i-1;
    		}
    		for (int j=0;j<len&&i*p[j]<=n;j++){
    			vis[i*p[j]]=1;
    			if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);
    			else{
    				phi[i*p[j]] = phi[i] * p[j];
    				break; 
    			}
    		}
    	}
    	phi[1]=1;
    	for (int i=2;i<=n;i++) phi[i]+=phi[i-1];
    	ll ans=0;
    	for (int i=0;i<len;i++) ans+=phi[n/p[i]]*2-1;
    	printf("%lld",ans);
    }

[Link 1]: http://oi.abcdabcd987.com/sieve-prime-in-linear-time/

发表评论取消回复

表情：

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

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

相关阅读

相关 GCD

GCD中也有一个类似于NSOperationQueue的队列，GCD统一管理整个队列中的任务。但是GCD中的队列分为并行队列和串行队列两类： • 串行队列：只

朱雀/ 2022年08月10日 00:37/ 0 赞/ 184 阅读

相关 BZOJ 2818——Gcd

题意：给定n，求gcd（x,y)==p 的对数，其中（1<=x<y<n) 思路：求`(x, y) = k, 1 <= x, y <= n`的对数等于求`(x,

喜欢ヅ旅行/ 2022年07月24日 08:09/ 0 赞/ 30 阅读

相关 BZOJ 2820 YY的GCD （莫比乌斯反演）

题目链接： [BZOJ 2820 权限题][BZOJ 2820] Description 神犇YY虐完数论后给傻×kAc出了一题。给定N,M ,求1<=x<=N,1<

分手后的思念是犯贱/ 2022年06月11日 04:40/ 0 赞/ 173 阅读

相关 GCD 定时器

![SouthEast][] [SouthEast]: /images/20220603/dff3667cacad496fa68bf9c0438243b3.png

淡淡的烟草味﹌/ 2022年06月03日 00:13/ 0 赞/ 119 阅读

相关欧几里得gcd/extend_gcd

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

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

相关 GCD

[GCD][] 什么是GCD 全称是Grand Central Dispatch。GCD 所有的API都在libdispatch.dylib动态库里面Xcode自动

蔚落/ 2022年03月22日 11:16/ 0 赞/ 196 阅读

相关 GCD Again

<table> <tbody> <tr> <td> <h1>GCD Again</h1> </td> </tr> <tr> <td>Tim

忘是亡心i/ 2021年12月24日 17:21/ 0 赞/ 245 阅读

相关 BZOJ2820:YY的GCD(莫比乌斯反演)

Description 神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种

怼烎@/ 2021年12月22日 05:41/ 0 赞/ 213 阅读

相关 GCD和扩展GCD

gcd(a, b)用于求解自然数a，b的最大公约数 int gcd(int a, int b) { if (b==0) return a;

傷城~/ 2021年10月29日 12:46/ 0 赞/ 355 阅读

相关 GCD / NSOperation

GCD 与 NSOperation 的区别 ? 1. GCD 是基于 C 语言写的核心服务, 非常简单高效, 而 NSOperation 是基于 GCD 的一种封装,抽象出

川长思鸟来/ 2021年09月29日 06:58/ 0 赞/ 346 阅读