首页 > 其他分享 >P2568 GCD

P2568 GCD

时间:2023-08-06 14:22:05浏览次数:38  
标签:prime lfloor frac GCD sum rfloor P2568 gcd

Question 问题 P2568 GCD

\[\sum_{p\in prime}\sum_{i=1}^n \sum_{j=1}^n [\gcd(i, j)==p] \]

Analysis 分析 1

(所以肯定有第二种思考的方法,看后面(目前没写))

变形

\[\sum_{p\in prime}\sum_{i=1}^{\lfloor{\frac n p}\rfloor} \sum_{j=1}^{\lfloor{\frac n p}\rfloor} [\gcd(i, j)==1] \]

改变枚举上界

\[\sum_{p\in prime}(\sum_{i=1}^{\lfloor{\frac n p}\rfloor}(2\sum_{j=1}^i[gcd(i,j)==1])-1) \]

容易发现后面的 \(\sum_{j=1}^i[gcd(i,j)==1]\) 就是 \(\varphi(i)\) 替换一下

\[\sum_{p\in prime}(2\sum_{i=1}^{\lfloor{\frac n p}\rfloor}\varphi(i)-1) \]

至此,该式子变换已经结束

我们只需要通过线性筛出 \(\varphi(i)\) 和 \(prime\)

做一个前缀和后 枚举所有\(p\in prime\) 并且 \(p\le n\)的所有情况就结束了

Code 代码

线性筛部分

void init(){
    phi[1]=1;
    for(int i=2;i<=n;i++){
		if(!f[i]) phi[i]=i-1,prime[++cnt]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
			f[prime[j]*i]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
}

主函数

int main(){
	cin>>n;init();
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+phi[i];
	for(int i=1;i<=cnt;i++) ans+=2*sum[n/prime[i]]-1;
	cout<<ans;
	return 0;
}

标签:prime,lfloor,frac,GCD,sum,rfloor,P2568,gcd
From: https://www.cnblogs.com/Mr-Az/p/Luogu-P2568.html

相关文章

  • P2257 YY的GCD
    传送门首先得到一个非常显然的柿子\[\sum_{p}\sum_{d}\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\]我们可以考虑T=pd,然后转化柿子\[\sum_{T}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{p|T}\mu(\frac{T}{p})\]后面这一块可以预处理。......
  • GCD
    GCD洛谷题目描述一张图有\(n\)个节点,编号为\(1,2,3,\dots,n\)。其中\(i\)号节点会向\(j\)号节点连一条边权为\(|i-j|\)的无向边,当且仅当\(\gcd(i,j)=i,\operatorname{lcm}(i,j)=j\)时连边。现询问\(q\)次,每次询问求\(x\)到\(y\)的最短路径。输入格式第一......
  • hdu7319 String and GCD
    StringandGCD首先我们需要用kmp的fail建树,然后需要利用到欧拉反演。\[n=\sum_{d|n}\varphi(d)\]对于这题来说\[(i,j)=\sum_{d|(i,j)}\varphi(d)=\sum_{d|i,d|j}\varphi(d)\]那么我们只需要用一个桶存每个约数从根到当前节点出现了多少次。然后枚举约数也有一个技巧,具体......
  • 【模板】数论基础:exGCD,exCRT,inverse,Lucas,BSGS,primitive root
    7.29数论WIP\(a\equivb\pmodp\Rightarrow\frac{a}{d}\equiv\frac{b}{d}\pmod{\frac{p}{d}},d=\gcd(a,b,p)\)。exGCD若\((a,b)=1\),则\(0\leqx<b\),\(ax\bmodb\)互不相同,有一个是\(1\)。证明:\(ax_1\equivax_2\pmodb\)则\((x_1-x_2)a|b\),因为......
  • 题解 HDU5726【GCD】/ LGT353762【Soso 的最大公约数】
    Problem给你一个长为\(N(1\leqN\leq1\times10^5)\)的整数序列:\(a_{1},\cdots,a_{n}(0<a_{i}\leq1\times10^9)\)。有\(Q(1\leqQ\leq1\times10^5)\)次提问。每次提问有个范围\(l,r\),你需要计算出\(\gcd(a_{l},,a_{l+1},...,a_{r})\),并且统计数对\((l’,r’......
  • 【蓝桥杯_真题演练】第十届C/C++省赛B组_H-等差数列(C++_gcd_数论)
    ProblemProcess在输入的时候先去重,然后进行排序,至于他们的公差p则需要计算每两个相邻数值之间差值的最大公因数,最终的结果应该是Code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,a[100010],cnt;set<int>s;intgcd(inta,intb){ returnb==......
  • UVA12716 GCD等于XOR GCD XOR
    UVA12716GCD等于XORGCDXOR一道数学题。 首先,我们可以知道,a-b>=gcd(a,b)=c;其次,a-b<=axorb=c;综上,可得a-b=c,即a-b=axorb.由于范围不大,直接枚举。第一层枚举c(因为c较少),第二层枚举a,(b=a-c) 再判断c是否等于a^b即可。#include<bits/stdc++.h>usingnamespacestd;......
  • [数论]Divisor and Gcd
    DivisorandGcd1、算术基本定理:n的质因数分解唯一一些常见结论:1.素数无限2.\(\lim_{n\rightarrow+\infty}n\prod\dfrac{n}{\frac{n}{\ln{n}}}\)(Π(n)表示<=n素数的个数)————即n以下素数个数大约是\(\frac{n}{\ln(n)}\)级别的3.\(Pn=O(nlogn)\)级别的(Pn表示素数)......
  • [ABC162E] Sum of gcd of Tuples (Hard)
    题面翻译给定\(n,k\),求\[\sum^k_{a_1=1}\sum^k_{a_2=1}\sum^k_{a_3=1}\dots\sum^k_{a_n=1}gcd(a_1,a_2,a_3,\dots,a_n)\mod\1000000007\]制約$2\\leq\N\\leq\10^5$$1\\leq\K\\leq\10^5$。思路点拨我们看到这么多\(\gcd\)的式子,我们自然想到莫比乌斯反演......
  • [数论]GCD&LCM&欧拉函——推柿子+例题
    GCD&LCM&欧拉函——推柿子一、\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(=\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\)\(=\phi(\frac{n}{d})\)二、\(\sum_{i=1}^{n}\gcd(i,n)\)\(\sum_{i=1}^{n}\gcd(i,......