撰写- 定义：d|n
- 算术基本定理的推论
- 正约数个数为：
(其中m为不重复的质因数个数，c为单个质因数的个数）
- 所有正约数的和：
- 求N的正约数集合——试除法：
-
const int MAXN=1e6+10; int factor[1600],m=0; for(int i=1;i*i<=n;i++) { if(n%i==0) { factor[++m]=i; if(i!=n/i)factor[++m]=n/i; } }
-
- 求1~N所有正约数集合
-
vector[500010] for(int i=1;i<=n;i++) { forj=1;j<=n/i;j++) factor[i*j].push_back(i); }
-
- 正约数个数为：
- 最大公约数
- 定义：记为gcd(a,b)
- 定理：gcd(a,b)*lcm(a,b)=a*b
- 更相减损术
-
ll gcd(ll a, ll b) { ifa == b) return a; if(a > b) return gcd(a-b, b); ifa < b) return gcd(a, b-a); }
-
- 欧几里得算法：
-
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
-
- 互质与欧拉函数
- 若gcd(a,b)=1则啊，b互质；gcd(a,b,c)=1,a，b，c互质；gcd(a,b)=gcd(a,c)=gcd(b,c)=1,a，b，c互质
- 欧拉函数：
-
//在线试除 ll euler(int n){ int p=n; for(int i=2;i<=sqrt(n);i++){//2开始 //玄学问题，用i*i作为判断条件过不了 if(n%i==0){ p=p/i*(i-1); while(n%i==0)n/=i; } } if(n>1){ p=p/n*(n-1); } return p; }//离线Eratoshenes筛 void euler(int n){ rep(i,2,n)phi[i]=i; rep(i,2,n) if(phi[i]==i) for(int j=i;j<=n;j+=i) phi[j]=phi[j]/i*(i-1); } //O(nlogn)//线性筛 int prime[1000045],cnt; int phi[1000045]; bool vis[1000045]; il void shai() { for(int i=2;i<=1000045;i++) { if(!vis[i])//su shu { prime[++cnt]=i; phi[i]=i-1;//xing zhi 1 } for(int j=1;j<=cnt;j++) { if(i*prime[j]>100000) break; vis[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=prime[j]*phi[i];//xing zhi 3 break; } else phi[i*prime[j]]=(prime[j]-1)*phi[i];//xing zhi 4 } } - 性质1：对于所有n>1，1~n中与n互质得数得和为n*phi(n)/2
- 性质2：若a，b互质，则phi(ab)=phi(a)phi(b)
-
- 积性函数：a，b互质，f(a,b)=f(a)*f(b)
- 性质3：若f是积性函数,
,则
- 性质4：若di|n,则F(n)=f(d1)+f(d2)+f(d3)+…+f(dk)也是积性函数
- 性质5：gcd是积性函数,欧拉函数是积性函数
- 性质6：n，m互质，gcd(i,n*m)=gcd(i,n)*gcd(i,m)
- 性质7：n的所有因子di的phi(di)的累加和为n
- 性质8：p为质数，若p|n且p|n^2，则phi(n)=phi(n/p)*p
- 性质9：p为质数，若p|n且！P|N^2，则phi(n)=phi(n/p)*(p-1)
- 性质10：p为素数，a为整数，phi(p^a)=p^a-p^(a-1)
- 性质3：若f是积性函数,
