《算法竞赛进阶指南》0x32_2约数

2024-08-30 12:04

本文主要是介绍《算法竞赛进阶指南》0x32_2约数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

定义
∀ a , b ∈ N , 若 g c d ( a , b ) = 1 , 则称 a , b 互质 \forall a,b \in \mathbb{N},若gcd(a,b)=1,则称a,b互质 a,bN,gcd(a,b)=1,则称ab互质
对于三个数或更多个数的情况,我们把 g c d ( a , b , c ) = 1 gcd(a,b,c)=1 gcd(a,b,c)=1的情况称为a,b,c互质。把 g c d ( a , b ) = g c d ( a , c ) = g c d ( b , c ) = 1 gcd(a,b)=gcd(a,c)=gcd(b,c)=1 gcd(a,b)=gcd(a,c)=gcd(b,c)=1称为a,b,c两两互质。后者显然是一个更强的条件。
欧拉函数
[1,N]中与N互质的数的个数被称为欧拉函数,记为 ϕ ( N ) \phi(N) ϕ(N)
若在算数基本定理中, N = p 1 c 1 p 2 c 2 . . . p m c m N=p_1^{c_1}p_2^{c_2}...p_m^{c_m} N=p1c1p2c2...pmcm,则:
ϕ ( N ) = N ∗ p 1 − 1 p 1 ∗ p 2 − 1 p 2 ∗ . . . ∗ p m − 1 p m = N ∗ ∏ 质数 p ∣ N ( 1 − 1 p ) \phi(N)=N*\frac{p_1-1}{p1}*\frac{p_2-1}{p2}*...*\frac{p_m-1}{pm}=N*\prod\limits_{质数p|N}(1-\frac{1}{p}) ϕ(N)=Np1p11p2p21...pmpm1=N质数pN(1p1)

证明:
设p是N的质因子,[1,N]中p的倍数有p,2p,3p,…,(N/p)*p,共N/p个。若q也是N的质因子,则[1,N]中q的倍数有N/q个。如果我们把这N/p+N/q个数去掉,那么p*q的倍数被去掉了两次,需要加一次回来。
因此[1,N]中不与N含有任何共同质因子p或q的数的个数为:
N − N p − N q + N p q = N ( 1 − 1 p ) ( 1 − 1 q ) N-\frac{N}{p}-\frac{N}{q}+\frac{N}{pq}=N(1-\frac{1}{p})(1-\frac{1}{q}) NpNqN+pqN=N(1p1)(1q1)
实际上这种思想叫做容斥原理,在N的全部质因子上使用容斥原理,可得到[1,N]中不与N含有任何公共质因子的数的个数,也就是与N互质的数的个数。

根据欧拉函数的计算式,我们只需要分解质因数,便可以顺便求出欧拉函数。

int phi(int n)
{int ans = n;for (int i = 2; i <= sqrt(n); i ++ )if (n % i == 0){ans = ans / i * (i - 1);while (n % i == 0) n /= i;}if (n > 1) ans = ans / n * (n - 1);return ans;
}

性质1-2
1. ∀ n > 1 , [ 1 , n ] 中与 n 互质的数的和为 n ∗ ϕ ( n ) / 2 \forall n > 1,[1,n]中与n互质的数的和为n*\phi(n)/2 n>1,[1,n]中与n互质的数的和为nϕ(n)/2
2. 若 a , b 互质 , 则 ϕ ( a b ) = ϕ ( a ) ∗ ϕ ( b ) 若a,b互质,则\phi(ab)=\phi(a)*\phi(b) a,b互质,ϕ(ab)=ϕ(a)ϕ(b)

证明:
因为 g c d ( n , x ) = g c d ( n , n − x ) gcd(n,x)=gcd(n,n-x) gcd(n,x)=gcd(n,nx),所以与n不互质的数x,n-x成对出现,平均值为n/2,因此与n互质的数平均值也是n/2,可得性质1。
根据欧拉函数的计算式,对a,b分解质因数直接可得性质2。

积性函数
如果a,b互质,有 f ( a b ) = f ( a ) ∗ f ( b ) f(ab)=f(a)*f(b) f(ab)=f(a)f(b),那么称函数f为积性函数。

性质3-6
3.若f是积性函数,且在算术基本定理中 n = ∏ i = 1 m p i c i n=\prod_{i=1}^{m}p_i^{c_i} n=i=1mpici,则 f ( n ) = ∏ i = 1 m f ( p i c i ) f(n)=\prod_{i=1}^{m}f(p_i^{c_i}) f(n)=i=1mf(pici)
4.设p为质数,若 p ∣ n p|n pn p 2 ∣ n p^2|n p2n,则 ϕ ( n ) = ϕ ( n / p ) ∗ p 。 \phi(n)=\phi(n/p)*p。 ϕ(n)=ϕ(n/p)p
5.设p为质数,若 p ∣ n p|n pn p 2 ! ∣ n p^2!|n p2!n,则 ϕ ( n ) = ϕ ( n / p ) ∗ ( p − 1 ) 。 \phi(n)=\phi(n/p)*(p-1)。 ϕ(n)=ϕ(n/p)(p1)
6. ∑ d ∣ n ϕ ( d ) = n \sum_{d|n}\phi(d)=n dnϕ(d)=n

证明:
性质3显然。
p ∣ n p|n pn p 2 ∣ n p^2|n p2n,则n,n|p包含相同的质因子,只是p的指数不同,把两者按照欧拉函数的计算公式写出,二者相除,商为p,所以性质4成立。
p ∣ n p|n pn p 2 ! ∣ n p^2!|n p2!n则p,n|p互质, ϕ ( n ) = ϕ ( n / p ) ∗ ϕ ( p ) \phi(n)=\phi(n/p)*\phi(p) ϕ(n)=ϕ(n/p)ϕ(p),而 ϕ ( p ) = p − 1 \phi(p)=p-1 ϕ(p)=p1,所以性质5成立。

利用线性筛求1到n所有数的欧拉函数

void init(int n)
{phi[1] = 1;for (int i = 2; i <= n; i ++ ){if (!st[i]){prime[cnt ++ ] = i;phi[i] = i - 1;}for (int j = 0; prime[j] * i <= n; j ++ ){st[i * prime[j]] = 1;if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j];//性质4break;}phi[i * prime[j]] = phi[i] * (prime[j] - 1);//性质5}}
}

acwing203.可见的点

如果所有的点与原点的连接构成直线 y = a b x y=\frac{a}{b}x y=bax的话,本题要求的就是在1到n范围内互质的(a,b)的对数是多少,按照y=x分成上下两部分,本题的答案即为 2 ∗ ϕ ( n ) + 1 2*\phi(n)+1 2ϕ(n)+1

#include <iostream>
using namespace std;
#define N 1010
bool st[N];
int prime[N];
int phi[N];
int cnt = 0;void init(int n)
{phi[1] = 1;for (int i = 2; i <= n; i ++ ){if (!st[i]){prime[cnt ++ ] = i;phi[i] = i - 1;}for (int j = 0; prime[j] * i <= n; j ++ ){st[i * prime[j]] = 1;if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j];break;}phi[i * prime[j]] = phi[i] * (prime[j] - 1);}}
}
int main()
{init(N - 1);int n, m;cin >> m;for (int T = 1; T <= m; T ++ ){int ans = 1;cin >> n;for (int k = 1; k <= n; k ++ ) ans += 2 * phi[k];cout << T << ' ' << n << ' ' << ans << endl;}return 0;
}

这篇关于《算法竞赛进阶指南》0x32_2约数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1120768

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI(简称 RVC)模型是一个基于 VITS(Variational Inference with adversarial learning for end-to-end Text-to-Speech)的简单易用的语音转换框架。 具有以下特点 简单易用:RVC 模型通过简单易用的网页界面,使得用户无需深入了

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费