理论

算数基本定理

算术基本定理可表述为：任何一个大于1的自然数 $N$,如果 $N$ 不为质数, 那么N可以唯一分解成有限个质数的乘积 $\boldsymbol{N}=\mathrm{P}_{1}^{ \mathrm{a}_{1} }\mathrm{P}_{2}^{ \mathrm{a}_{2}} \ldots \ldots \mathrm{P}_{\mathrm{n}}^{ \mathrm{a}_{\mathrm{n}}}$, 这里 $\mathrm{P}_{1<} \mathrm{P}_{2<} \mathrm{P}_{3} \ldots \ldots<\mathrm{P}_{\mathrm{n}}$ 均为质数, 其中指数 $\mathrm{a}_{\mathrm{i}}$ 是正整数。这样的分解称为 $\boldsymbol{N}$ 的标准分解式。

约数个数

如果 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)

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
bool st[N];
int primes[N],cnt;

void get_prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])  primes[cnt++] = i;
        for(int j=0;primes[j]*i<=n;j++){
            int t=primes[j]*i;
            st[t] = true;
            if(i%primes[j] == 0) break;
        }
    }
}

欧几里得算法

1
2
3
int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

贝祖定理

指对于任意正整数对(a,b)，一定存在非零整数x和y，使得 ax+by=gcd(a,b)；

算法：拓展欧几里得算法

我们来分情况讨论一下扩展欧几里得定理：
(1)当b = 0时，a和b的最大公约数为a.则x = 1;
(2)当b ≠ 0时，by+(a mod b)x = gcd(a,b) ——> ax+b(y - a/b * x) = gcd(a,b)

即当我们用扩展欧几里得定理求x和y时，欧几里得定理每递归一次x不用变,y->y-a/b * x即可

1
2
3
4
5
6
7
8
9
LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

欧拉函数

欧拉函数的定义
$1 \sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数, 记为 $\phi(N)$ 。 若在算数基本定理中, $N=p_{1}^{a_{1}} p_{2}^{a_{2}} \ldots p_{m}^{a_{m}}$, 则:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//求欧拉函数
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}


//筛法
int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

X的因子链

题意：输入正整数 X，求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度，以及满足最大长度的序列的个数。

题解：先对 X 求质因数，根据算数基本定理，质因数的数目就是最大长度。然后用排列组合求最大长度的序列的个数。其中需要用到线性筛。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = (1<<20)+10,M=30010,INF = 0x3f3f3f3f;
bool st[N];
int primes[N],cnt;
int minp[N];
LL jc[22];

void get_prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])  primes[cnt++] = i,minp[i]=i;
        for(int j=0;primes[j]*i<=n;j++){
            int t=primes[j]*i;
            st[t] = true;
            minp[t] = primes[j];
            if(i%primes[j] == 0) break;
        }
    }
}

int main(){
    int x;
    get_prime(N-1);
    jc[1]=1;
    for(int i=2;i<=20;i++){
        jc[i]=jc[i-1]*i;
    }
    while(~scanf("%d",&x)){

        map<int,int> mp;
        int cnnt=0;
        while(x>1){
            int temp=minp[x];
            x/=minp[x];
            mp[temp]++;
            cnnt++;
        }
        LL ans=jc[cnnt];
        for(auto tp:mp){
            ans/=jc[tp.second];
        }
        printf("%lu %lld\n",cnnt,ans);
    }
    return 0;
}

技巧总结：用到了多次询问求一个数质因数的方法，先线性筛预处理minp[]，再除。

聪明的燕姿

题意：给定S，求所有正约数之和等于 S 的数。

思考：设这个数为X = $p_1^{c_1} p_2^{c_2} … p_k^{c_k}$，那么$S = (p_1^0 + p_1^1 + … + p_1^{c_1}) … * (p_k^0 + p_k^1 + … + p_k^{c_k})$

用暴搜来做，先搜Pi，再搜Ci。剪枝：$p_i<\sqrt{S}$。i>=2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 50000,M=30010,INF = 0x3f3f3f3f;
bool st[N];
int primes[N],cnt;
int ans[N],len;

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i] = true;
            if(i %primes[j] == 0) break;
        }
    }
}
bool is_primes(int x)
{
    if (x < N) return !st[x];
    for (int i = 0; primes[i] <= x / primes[i]; i ++ )
        if (x % primes[i] == 0)
            return false;
    return true;
}

void dfs(int last,int prod,int s){
    if(s==1){
        ans[len++] = prod;
        return;
    }

    if(s-1>( last<0 ?1:primes[last]) && is_primes(s-1))
        ans[len++] = prod *(s-1);

    for(int i = last +1;primes[i] <= s / primes[i];i++){
        int p = primes[i];
        for (int j = 1 + p, t = p; j <= s; t *= p, j += t)
            if (s % j == 0)
                dfs(i, prod * t, s / j);
    }

}

int main(){
    get_primes(N-1);

    int s;
    while(cin>>s){
        len = 0;
        dfs(-1,1,s);

        cout<<len<<endl;

        if(len){
            sort(ans,ans+len);
            for(int i=0;i<len;i++) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

技巧总结：一点数论+暴搜+剪枝

五指山

题意：这题的题意是让我们求x+bd = y+an ,整理得：-an+bd = y-x

但是我们得扩展欧几里得定理只能求 -an+bd = gcd(n,d)中的a和b，但是很容易看出y-x应该为gcd(n,d)的整数倍，否则无解。

若有解我们利用扩展欧几里得定理就可以求得-an+bd = gcd(n,d)中的a和b，然后将a和b扩大 (y-x)/gcd(n,d)倍

思考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        LL n,d,x,y,a,b;
        scanf("%lld%lld%lld%lld",&n,&d,&x,&y);

        int gcd = exgcd(n,d,a,b);
        if((y-x)%gcd){
            printf("Impossible\n");
        }else{
            b*=(y-x)/gcd;
            n/=gcd;
            printf("%lld\n",(b%n+n)%n);
        }
    }
    return 0;
}

技巧总结：拓展欧几里得算法的应用

最大比例

题意：M 级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值（如3/2）。

随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。

思考：

假设原数列为 a,a*(p/q)^1,a*(p/q)^2,...,a*(p/q)^(n-1)
假设抽取的数列 b0,b1,…,b(N-1) (从小到大排好序了)

b1/b0,b2/b0,...,b(N-1)/b0--> (p/q)^x1,(p/q)^x2,...,(p/q)^x(N-1)
我们要求的是:（p/q）^k , (p/q)>1,所以使k最大，即求 x1~x(N-1)的最大公约数

这里我们使用更相减损术，因为我们没有得到确切的x1~x(N-1)是多少，我们只有(p/q)^x1,(p/q)^x2,…,(p/q)^x(N-1)这些的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>

using namespace std;

const int N=110;

typedef long long LL;

LL x[N],a[N],b[N];
int cnt=0;
LL gcd(LL a,LL b)
{
    return b? gcd(b,a%b):a;
}

LL gcd_sub(LL a,LL b)
{
    if(a<b)  swap(a,b);  //更相减损术总是大减小（它们的底数是一样的）
    if(b==1)  return a;
    return gcd_sub(b,a/b);
}

int main()
{
    int n;
    cin>>n;

    for(int i=0; i<n; i++)  scanf("%lld",&x[i]);

    sort(x,x+n);

    for(int i=1; i<n; i++)
    {
        if(x[i] != x[i-1])
        {
            LL d=gcd(x[i],x[0]);
            a[cnt]=x[i] / d;  //得到x[i]/x[0]的分子
            b[cnt]=x[0] / d;  //得到x[i]/x[0]的分母
            cnt++;
        }
    }

    LL up=a[0],down=b[0];
    for(int i=1; i<cnt; i++)
    {
        up=gcd_sub(up,a[i]);  //两两求最大公约数
        down=gcd_sub(down,b[i]);
    }

    cout<<up<<"/"<<down<<endl;

    return 0;
}

技巧总结：

可见的点（欧拉函数）

题意

简单应用

思考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>

using namespace std;
const int N=1010;

int cnt,primes[N],euler[N];
bool st[N];
int n,c;

void init(int n){
    euler[1]=1;
    
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            euler[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0){
                euler[t]=euler[i]*(primes[j]);
                break;
            }
            euler[t]=euler[i]*(primes[j]-1);
        }
    }
}

int main(){
    scanf("%d",&c);
    init(1000);
    
    for(int i=1;i<=c;i++){
        scanf("%d",&n);
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=(euler[i]);
        }
        ans<<=1;
        ans+=1;
        cout<<i<<" "<<n<<" "<<ans<<endl;
    }
}

最大公约数(欧拉函数)

题意

给定整数 $N$, 求 $1 \leq x, y \leq N$ 且 $G C D(x, y)$ 为素数的数对 $(x, y)$ 有多少对。

思考

统计 $\operatorname{gcd}(x, y)=p \in[0, N]$ 对数 $\Longleftrightarrow$ 统计 $\operatorname{gcd}\left(\frac{x}{p}, \frac{y}{p}\right)=1 \in\left[0, \frac{N}{p}\right]$ 对数 $\Longleftrightarrow x^{\prime}, y^{\prime} \in\left[0, \frac{N}{p}\right]$ 互质数的对数

优化：用前缀和处理欧拉函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
const int N=10000010;

int cnt,primes[N],euler[N];
LL sum[N];
bool st[N];
int n,c;

void init(int n){
    
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            euler[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0){
                euler[t]=euler[i]*(primes[j]);
                break;
            }
            euler[t]=euler[i]*(primes[j]-1);
        }
    }
     for(int i=1;i<=n;i++) sum[i]=sum[i-1]+euler[i];
}

int main(){
    scanf("%d",&n);
    init(n);
   
    LL ans=0;
    for(int i=0;i<cnt;i++){
        int t=n/primes[i];
        ans+=sum[t]*2+1;
    }
    
    cout<<ans<<endl;
}

技巧总结：