分解质因数
inline void divide(int x){
for(int i=2;i*i<=x;++i){
if(x%i==0){
int cnt=0;
while(x%i==0){
x/=i;
cnt++;
}
printf("%lld %lld
",i,cnt);
}
}
if(x>1)printf("%lld %lld
",x,1);
//可能是一些大数没有可以除的数字存在所以要特判
puts("");
}
试除法求约数
note:* 可以只遍历一半，另一半由x/i O(1)求
#define N 1000010
int n,tot;
int p[N];
bool ip[N];
inline void divide(int x){
mem(p,0);
tot=0;
for(int i=1;i*i<=x;++i){
if(x%i==0){
p[++tot]=i;
if(x/i!=i)
p[++tot]=x/i;
}
}
sort(p+1,p+tot+1);
rep(j,1,tot)
printf("%lld ",p[j]);
puts("");
}
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
约数个数 坑题
SOL：
约数个数即每个（质因数的个数+1）相乘，因为对于每个质因数，你有选0,1,2,...此质因数的个数 种选法，乘法原理一下就好啦
note:
* unordered_map 不能在本地运行………………
* 为防止桶开不下（2e9）,用unordered_map来维护下一个的位置
#define mod 1000000007
#define N 10000010
int n,ans=1;
unordered_map<int,int> p;
inline void count(int x){
for(int i=2;i*i<=x;++i){
while(x%i==0){
p[i]++;
x/=i;
}
}
if(x>1)p[x]++;
}
#undef int
int main(){
#define int long long
//freopen("yueshu.txt","r",stdin);
rd(n);
while(n--){
int x;rd(x);
count(x);
}
int res=1;
for(unordered_map<int,int>::iterator it=p.begin();it!=p.end();it++){
res=res*(it->second+1)%mod;
}
printf("%lld",res%mod);
return 0;
}
欧拉函数
当p[],ip[]必须开到2e9,你是否会感到绝望？
那你就不要用线性求欧拉函数嘛，用公式啊喂
用公式需注意：
ϕ(N) = N∗(p1−1/p1)∗(p2−1/p2)∗…∗(pm−1/pm)
最好先/后*,我说的是最好
注意考虑（x>1）的情况（x是个质数）
/*
reference:
translation:
solution:
trigger:
note:
*
record:
date:
2019.08.28
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
#undef int
int main(){
#define int long long
#ifdef WIN32
freopen("","r",stdin);
#endif
int n;rd(n);
while(n--){
int x;rd(x);
int ans=x;
for(int i=2;i*i<=x;++i){
if(x%i==0){
ans=ans/i*(i-1); //防止溢出
while(x%i==0) x/=i;
}
}
if(x>1) ans=ans/x*(x-1);
printf("%lld
",ans);
}
return 0;
}
-
质数i的欧拉函数即为phi[i]=i-1;
1 ~ i−1均与i互质，共i−1个。 -
phi[p[j] * i]分为两种情况：
- ① i%p[j]==0时：p[j]是i的最小质因子，也是p[j]* i的最小质因子，因此(1-1/p[j])这一项在phi[i]中计算过了，只需将基数N修正为p[j]倍，最终结果为phi[i]* p[j]。
- ② i%p[j]!=0：p[j]不是i的质因子，只是p[j]* i的最小质因子，因此不仅需要将基数N修正为p[j]倍，还需要补上(1-1/p[j])这一项，因此最终结果phi[i]* (p[j]-1)。又因为p[j]是质数，所以又可以写作(phi[p[j]])
真.欧拉筛
#define N 1000010
int p[N],phi[N],tot;
bool ip[N];
inline void Euler(){
mem(ip,1);
ip[1]=0;
phi[1]=1;
rep(i,2,N){
if(ip[i]){
p[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot && i*p[j]<=N;++j){
ip[i*p[j]]=0;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
else phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}