分解质因数

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\n",i,cnt);
        }
    }
    if(x>1)printf("%lld %lld\n",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\n",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]];
        }
    }
}

【acwing板子大全】数论