数论

数论

约数个数

• 对于求解可以使用质因数分解的方式

  $f(N)$ = $(C_1 + 1) (C_2 + 1)$……$(C_k + 1)$

  $N$ = $P_1^{C_1}$$P_2^{C_2}$……$P_k^{C_k}$

时间复杂度

$1$ ~ $N$ 中,$\sum\limits_{i=1}^N = Nlog(N)$

int 范围内，$MAXf(N)$ = 1600

求约数的方法详见[例题]([P1072 NOIP2009 提高组] Hankson 的趣味题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

code

#include <bits/stdc++.h>
#define int long long 
using namespace std ;
const int maxn = 5e4 + 10 ;
int m , n , ans ;
struct node//存每个质因子
{
    int p , c ;//质因子，质因子的次数
}factor[1605] ;//int 范围内最多的约数的个数
int tot , cnt , num ; // 每个质因子的个数 , 约数的个数
int prime[maxn >> 1] , di[maxn] ;
bool is_prime[maxn] ;
void erlu(int x)
{
    for(int i = 2 ; i <= x ; i++)
    {
        if(! is_prime[i])   prime[++num] = i ;
        for(int j = 1 ; prime[j] <= x / i ; j++)
        {
            is_prime[prime[j] * i] = true ;
            if(! (i % prime[j]))  break ;
        }
    }
}
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
void dfs(int u ,int p)
{
    if(u > tot)
    {
        di[++cnt] = p ;
        return ;
    }
    for(int  i = 1 ; i <= factor[u].c + 1 ; i++)
    {
        dfs(u + 1 ,p) ;
        p *= factor[u].p ;
    }
}
signed main()
{
    int a, b , c , d ;
    cin >> n ;
    erlu(maxn - 1) ;
    while(n--)
    {
        cin >> a >> b >> c >> d ;//b1,c是d的约数
        int t = d ; tot = 0 ;
        for(int i = 1 ; prime[i] <= t / prime[i] ; i++ )
        {
            int p = prime[i] ;
            if(! (t % p))//是d的质因子
            {
                int c = 0 ;
                while(! (t % p))  t /= p , c++ ;
                factor[++tot] = {p , c} ;
            }
        }//试除法的原理实现
        if(t > 1)//循环除的情况下，说明t也是d的质因子
            factor[++tot] = {t , 1} ;
        cnt = 0 , ans = 0 ;   
        dfs(1 , 1) ;//爆搜处理处所有的约数
        //cout <<cnt<<" " << num<<" " << tot<<" " ;
        for(int i = 1 ; i <= cnt ; i++ ) 
        {
            int x = di[i] ;
            if(gcd(a , x) == b && c * x / gcd(x , c) == d)  ans++ ;
        }
        cout << ans ;
        puts("") ;
    }
    return 0 ;
}

线性筛

法求欧拉函数

如果 $p_j$ 是 $i$ 的最小质因子

$$φ(p_j \times i ) = φ(i) \times prime_j$$

如果 $p_j$ 不是 $i$ 的最小质因子

$$φ(p_j \times i ) = φ(i) \times (prime_j - 1)$$

如果 $i$ 是质数

$$φ(i) = i - 1$$

code

void erlu(int n)
{
    phi[1] = 1 ; 
    for(int i = 2 ; i <= n ; i++)
    {
        if(! is_prime[i])
        {
            phi[i] = i - 1 ;
            prime[++cnt] = i ;
        }
        for(int j = 1 ; prime[j] <= n / i ; j++ )
        {
            is_prime[prime[j] * i] = true ;
            if( i % prime[j] == 0 )
            {
                phi[prime[j] * i] = phi[i] * prime[j] ;
                break ;
            }
            phi[prime[j] * i] = phi[i] * ( prime[j] - 1 ) ;
         }
    }
}

以上性质在代码中均有体现

欧拉函数的其他性质

1. 通式
   

   $$φ(n) = n \times (1 - \dfrac{1}{p_1})\times (1 - \dfrac{1}{p_2})……(1 - \dfrac{1}{p_k})$$
   $p_i$是根据唯一分解定理分解出来的 $n$ 的质因子

2. 若 $a$ , $b$ 互质
   

   $$φ(ab) = φ(a) \times φ(b)$$

3. $p$ 为质数
   

   $$φ(p^n) = p^n - p^{n-1}$$

欧拉定理和费马小定理

欧拉定理

若正整数 $a$ 和 $n$ 互质，则 $a^{φ(n)} \equiv 1 (\mod n\ )$

$a\times a_1 \% n$ 是1~n中的一个质数

证明：

若 $a\times a_1 \% n$ 不是1~n中的一个质数，那么$a\times a_1 \% n$ = $kn + b$ , 其中$b$是$n$的一个因子，那么 $a\times a_1$ 即 $kn + b$ 和 $n$ 有一个因子 b 和 a 。

费马小定理

欧拉定理的条件下，若 $n$ 是一个质数，那么

$$a^{p-1} \equiv 1 (\mod p\ )$$
证明：

用欧拉函数的引理把 $φ$ 替换掉就行了 。

应用：
费马小定理可以用来求乘法逆元
逆元：
若 $a⋅x≡1(\mod b\ \ )$
则称 $x$ 是 $a$ 在mod $b$ 意义下的逆元
例题
题意，求 $a_i$ 在 mod $p_i$ 意义下的最小逆元。

$$a_i⋅x\equiv 1(\mod p_i \ )$$
首先利用费马小定理，构造处一组解
$$a_i ^ {p_i - 1} \equiv 1(\mod p_i \ ) \ \ \ \ \ \ \ \Rightarrow\ \ \ \ \ \ \ a_i ⋅ a_i^{p_i-2}\equiv1(\mod p_i \ )$$
这里的 $a_i^{p_i-2}$ 为 $a_i$ 在 mod $p_i$ 意义下的最小逆元 ， 即为所求 $x$。
这里使用快速幂求解 $a_i^{p_i-2}$ ，模数即为 $p_i$ 。
最后考虑无解的情况，根据费马小定理的使用条件，要保证 $a_i$ 与 $p_i$ 互质。所以对于 $a_i$ % $p_i$ = $0$ 的情况直接特判掉，输出 $“impossible”$ 。