约数

题目

• 洛谷: 反素数 难 　(值得一做)
  \(大意\)? 定义"反素数": 对于任意的 0 g(i) (g(x)为x的约数个数) 则x为反素数.　求不大于N的最大反素数
  \(简析\)? 1~INT_MAX 中任何数的不同质因子都不会超过10个. 且所有质因子指数的总和不会超过30
  AC代码

• 洛谷: 余数之和 难 除法分块
  \(大意\) 计算 \(G(n, k) = \sum_i^nk\ mod\ i\)
  [AC代码] 待补

• 洛谷: Hankson的趣味题 典 难
  \(大意\) 求有多少个x满足 \(\gcd(a,b)=c\ 且\ lcm(b,x)=d\)
  [AC代码] 待补

• 洛谷: 仪仗队 典　求\(\varphi (n)\)?的两种方法
  \(大意\) 从正方形点阵的左下角(0, 0) 向四周看去, 能看到多少个点?
  \(简析\) 一个点(x,y)能被(0,0)看到 当且 \(\gcd(x,y)=1\)???(除(1,0), (0,1)外)
  Ac代码

• 轻拍牛头 约数

  \(大意\) 给定N个数, 对于任意一个数, 求出, 其它N-1个数有多少个能够整除它. 　(\(N≤10^5, M≤10^6\))

  \(简析\) 用一个桶 装下那N个数值.　再对每个数 求约数, 累加即可.　(\(O(n\sqrt A)\)?)

  AC代码

• 樱花 典 难　(值得一做)

  \(大意\) 给定n, 求有多少个正整数数对\((x,y)\) 满足 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\)

  \(题解\)

算法

约数

• 求正约数集合
  1. 试除法 推论:N的约数个数上界为 2√N
  2. 倍数法 推论: 1~N约数个数总和NlogN
  3. 算术基本定理 + DFS
• 算术基本定理: \(N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\)
• 正约数个数 \(\prod_{i=1}^m(c_i+1)\)
• 正约数之和 \(\prod\limits_{1≤i≤m}(\sum\limits_{0≤j≤c_i}(p_i)^j)\)

GCD与LCM

• 定理 \((a,b)[a,b]=ab\)
• 九章算术 · 更相减损术 \((a,b)=(b,a-b)=(a,a-b)\)　\((2a,2b)=2(a,b)\)
• 欧几里得算法 \((a,b)=(b,a \mod b)\) 　\(O(log(a+b))\)

  int gcd(int a, int b){
  	while(b^=a^=b^=a%=b);
  	return a;
  }
  

互质与欧拉函数

若 \(\gcd(a,b)=1\)则 a,b 互质. 所以 1 与任何正整数均互质

将 1~N 中 与N互质的数的个数 记为: \(\varphi(N)\)

• 计算定理: 在算术基本定理中有: \(\varphi(N)=N\prod\limits_{质数p|N}(\frac{p-1}{p})\)

  // 单个计算
  int Phi(int x){ //求欧拉函数.  批注: phi(1)=1
  	int ans=x;
  	for(int p=2; p<=x/p; ++p)
  		if(x%p==0){
  			ans=ans/p*(p-1);
  			while(x%p==0) x/=p;
  		}
  	if(x>1) ans=ans/x*(x-1);    // 这句不要漏啊!	不写成 ans*=(x-1)/x 
  	return ans;
  }
  

• 递推性质

  1. 设 p 为质数, 若 \(p\mid n 且 p^2\mid n\) 则\(\varphi(n)=\varphi(\frac{n}{p})×p\)
  2. 设 p 为质数, 若 \(p\mid n 且 p^2\nmid n\) 则\(\varphi(n)=\varphi(\frac{n}{p})×(p-1)\)

  // 递推 phi(1~n)
  void euler(int n){  // O(N) 欧拉线性筛
  	phi[1]=1;
  	REP(i, 2, n){
  		if(!v[i]){  // i为质数
  			v[i]=i, prime[++m]=i,
  			phi[i]=i-1;	// 注意要对 phi[i]=i-1 进行初始化
  		}
  		REP(j, 1, m){
  			int p=prime[j];
  			if(p>v[i] || p>n/i) break;
  			v[p*i]=p, phi[p*i] = phi[i]*(i%p ?p-1 :p);  /* 欧拉函数的重要性质 */
  		}
  	}
  }
  

• 积性函数
  若当 a,b 互质时, 若\(f(ab)=f(a)×f(b)\) 则 函数f 为积性函数
  \(\varphi(x)\) 是积性函数
  积性函数f 若 \(n=\prod_{i=1}^mp_i^{c_i} \ 则 \ f(n)=\prod_{i=1}^mf(p_i^{c_i})\)

• 其他性质

  1. \(\forall n>1\) 1~n中与n互质的数的和为 \(\frac{n·\varphi(n)}{2}\)
  2. \(\sum_{d|n}\varphi(d)=n\)