专题四 数论

2025ACM寒假集训

专题四 数论

102400226 石华波

Vjudge账号:DustLi

问题一 有理数取余

问题陈述

给出一个有理数 c = $\frac{a}{b}$，求$c mod 19260817$的值。

这个值被定义为 $bx ≡ a (mod 19260817)$ 的解。

输入

一共两行。

第一行，一个整数 $a$。 第二行，一个整数 $b$。

输出

一个整数，代表求余后的结果。如果无解，输出 Angry!。

解题思路

设$19260817$为$M$，那么$bx ≡ a(mod M)$,根据同余方程的性质，可得出$b\frac{x}{a} ≡ 1(modM)$,将$\frac{x}{a}$视为一个整体，设为$z$，那么,$bz ≡ 1(modM)$，这是一个比较常见的同余方程，由于$a$已知，只需要求出$z$的值，就可以求出$x$。

同时，为了避免$a、b$过大，在读入时不断对$M$取余。

得出的$z$可能是个负数，通过$ z=(z%M+M)%M$处理，保证最后的结果为正数。

AC代码：

 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

#include<algorithm>
#include<iostream>
#include<tuple>

#define ll long long

using namespace std;

const ll Mod=19260817;

tuple<ll,ll,ll> ExGcd(ll a,ll b) {
    if(b==0) return {a,1,0};
    auto [G,x1,y1]=ExGcd(b,a%b);
    ll x=y1;
    ll y=x1-a/b*y1;
    return {G,x,y};
}

ll GetMod() {
    ll Res=0;
    char ch=getchar();
    while(!isdigit(ch)&&ch!=EOF) ch=getchar();
    while(isdigit(ch)) {
        Res=Res*10+ch-'0';
        Res%=Mod;
        ch=getchar();
    }
    return Res;
}

int main() {
    ll a,b;
    a=GetMod();
    b=GetMod();
    if(b==0) cout<<"Angry!"<<endl;
    else {
        auto [G,x,y]=ExGcd(b,Mod);
        x=(x%Mod+Mod)%Mod;
        ll ans=a*x%Mod;
        cout<<ans<<endl;
    }
    return 0;
}

问题二 Minimal Coprime

问题陈述

给定$ [l,r]$，一个正整数的区间，找出包含在$ [l,r]$中的最小互质区间的数量。

解题思路

显然，$x$与$x+1$是互质的，最小互质区间必定为$[x,x+1]$，所以在区间$[l,r]$中，总共有$r-l$个最小互质区间。

这里特判$[1,1]$，与其他$[x,x]$类型的区间不同，$1$与$1$是互质的。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include<iostream>

#define ll long long

using namespace std;

int main() {
    int N;
    cin>>N;
    while(N--) {
        int a,b;
        cin>>a>>b;
        if(a==b&&a==1) cout<<1<<endl;
        else cout<<b-a<<endl;
    }
    return 0;
}

问题三 素数密度

问题陈述

给定 $L,R$，请计算区间 $[L,R]$中素数的个数。

$1≤L≤R≤2^{31}，R-L≤10^6$

解题思路

题目数据范围极大，直接用线性筛也会超时。

但是，题目告知$L,R$之差不超过$10^6$，我们可以尝试标记区间中的每一个合数。

$R$小于$INT_MAX$，因为合数必定可以表示为数个质数的积，且一定有至少一个因数$≤\sqrt{R}$，所以我们只需要筛出$[1,\sqrt{INT_MAX}]$范围内的质数，然后再用这些质数通过筛法来标记区间内合数，就可以求出区间内质数的个数。

AC代码：

 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

#include<iostream>

#define ll long long

using namespace std;

int Prime[50001];
bool isComposite[50001];
bool isCompositeLR[1000001];
int cnt=1;

void LinearSieve(){
    for(int i=2;i<=50000;i++) {
        if(!isComposite[i]) Prime[cnt++]=i;
        for(int j=1;i*Prime[j]<=50000;j++) {
            isComposite[i*Prime[j]]=true;
            if(i%Prime[j]==0) break;
        }
    }
}

int main() {
    LinearSieve();
    int l,r;
    cin>>l>>r;
    l+=l==1;
    int ans=0;
    for(int i=1;i<cnt;i++) {
        if(Prime[i]>r) break;;
        int p=Prime[i];
        ll SL=(l+p-1)/p*p>2*p?(l+p-1)/p*p:2*p;
        for(ll j=SL;j<=r;j+=p) isCompositeLR[j-l+1]=true;
    }
    for(int i=1;i<=r-l+1;i++) {
        ans+=!isCompositeLR[i];
    }
    cout<<ans<<endl;
    return 0;
}

问题4 最大公约数和最小公倍数问题

问题陈述

输入两个正整数 $x_0,y_0$，求出满足下列条件的 $P,Q$ 的个数：

  1. $P,Q$ 是正整数。
  2. 要求$P,Q$ 以 $x_0$ 为最大公约数，以$y_{0}$ 为最小公倍数。

试求：满足条件的所有可能的$P,Q$ 的个数。

解题思路

$GCD$和$LCM$有一条性质，$GCD×LCM=a×b$，所以，$x_0×y_0=P×Q$，设$x_0×y_0=M$，我们只需要在小于$M$的范围内搜寻能够整除$M$的数，然后验证这个数与$M$除以这个数的商的最大公约数是不是$x_0$即可。

由于同一对$P,Q$调换顺序算作另一个解，每次处理时令$ans+2$，遇到$x_0=y_0$时，在最终答案上$-1$即可。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include<iostream>

#define ll long long

using namespace std;

ll Gcd(ll a,ll b) {
    if(b==0) return a;
    return Gcd(b,a%b);
}

int main() {
    ll n,m;
    int ans=0;
    cin>>n>>m;
    if(m==n) ans--;
    ll s=n*m;
    for(ll i=1;i*i<=s;i++) if(s%i==0&&Gcd(i,s/i)==n) ans+=2;
    cout<<ans<<endl;
    return 0;
}

问题五 Longest Subsequence

问题陈述

给你一个包含 $a$ 个元素的数组 $n$，以及一个数字 $m$。考虑数组 $a$的某个子序列，并计算其元素的最小公倍数$(LCM)$的值。将最小公倍数表示为$l$。找出任意一个值为 $l ≤ m$ 的最长子序列 $a$。

子序列是从 $a$ 中删除一些元素后得到的数组。可以删除零个或所有元素。

空数组的最小公倍数等于 $1$。

解题思路

使用多个数组，$Src$存储原始数据，数组下标即为数据序号。$Tms$存储每个数字出现的次数，避免重复处理浪费时间，用$Len$来存放其下标对应数字所对应的子序列。

处理数据时，可以忽略大于$m$的数据。

通过筛的方法找到最大的$l$之后，直接遍历一遍$Src$，输出能够整除$l$的数据的下标即可。

AC代码：

 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

#include<iostream>

#define ll long long

using namespace std;

const int MaxN=1e6+1;

int n,m;
int Src[MaxN];
int Tms[MaxN];
int Len[MaxN];

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>Src[i];
        if(Src[i]<=m) Tms[Src[i]]++;
    }
    for(int i=1;i<=m;i++) {
        if(Tms[i]==0) continue;
        for(int j=i;j<=m;j+=i) {
            Len[j]+=Tms[i];
        }
    }
    int MaxL=0;
    int MaxCnt=0;
    for(int i=1;i<=m;i++) {
        if(Len[i]>MaxCnt) {
            MaxCnt=Len[i];
            MaxL=i;
        }
    }
    if(MaxL>0) {
        cout<<MaxL<<" "<<MaxCnt<<endl;
        for(int i=1;i<=n;i++) if(MaxL%Src[i]==0) cout<<i<<" ";
    }
    else cout<<1<<" "<<0<<endl;
    return 0;
}

问题六 Common Generator

对于两个整数$x$和$y(x,y\geq2)$，我们将说$x$是$y$的一个生成器当且仅当$x$可以通过执行以下操作若干次(可能为零)转换为$y$：

  • 选择一个除数$d(d\geq2)$，然后将$x$增加$d$。 例如，
  • $3$是$8$的一个生成器，因为我们可以执行以下操作：$\begin{aligned}3&\overset{d=3}{\longrightarrow}6\&\overset{d=2}{\longrightarrow}8;\end{aligned}$
  • $4$是$10$的一个生成器，因为我们可以执行以下操作：$\begin{aligned}4&\overset{d=4}{\longrightarrow}8\&\overset{d=2}{\longrightarrow}10;\end{aligned}$
  • $5$不是$6$的一个生成器，因为我们无法通过上述操作将$5$转换为$6$。 现在，Kevin给你一个数组$a$，它由$n$个成对不同的整数组成$(a_i\geq2)$。 你必须找到一个整数$x\geq2$，使得对于每个$1\leq i\leq n$，$x$是$a_i$的一个生成器，或者确定这样的整数不存在。

解题思路

$2$可以是任意一个非素数的生成器，对于偶数，这点显而易见。对于奇数，一个不是素数的奇数$x$总有一个除$1$以外的奇数因数，称之为$f(x)$，显然$x-f(x)$是一个偶数，可以由$2$生成，而$f(x)$也是$x-f(x)$的一个因数，故$2$可以是任意一个非素数奇数的生成器。

对于素数而言，它的生成器只能是它本身。设$z$是一个素数，如果它有除了它本身以外的生成器，那么一定存在$m$使得$m+f(m)=z$，显然，这与$z$是一个素数矛盾。所以，当数组中含有两个及以上的素数时，该例无解。

对于只含有一个素数的数组，该例如果有解，解一定是该素数。素数显然不能生成小于自己的、或者大小介于自己的$1-2$倍之间的数：因为此时它只有它本身一个不为$1$的因数。但是当要生成的数大于它的两倍时，情况不同。我们设这个素数为$z$，对于大于$2z$的数，我们可以先生成$2z$，获得一个因数:$2$后，就可以生成其他数了。所以，素数可以生成大于等于自己两倍的偶数。对于奇数，设这个奇数为$x$，那么如果$x-f(x)≥2z$，那么这个奇数也是可以由$z$生成的。

所以，我们要做的事情是：先筛出数据范围内的所有素数，在读入数据时，分三种情况讨论:

1.素数的数量大于等于二，可以直接输出$-1$。

2.素数的数量为零，可以直接输出$2$。

3.素数的数量为一，那么我们就要用上面的方法对数组中的每一个数据进行检查，如果每一个数据都能被这个素数生成，那么输出这个素数，否则输出$-1$。

AC代码：

 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

#include<iostream>

#define ll long long

using namespace std;

const int MaxN=4e5+1;

int t,n;
int a[100001];
int Prime[MaxN];
int isComposite[MaxN];
int cnt=1;

void LinearSieve(){
    for(int i=2;i<MaxN;i++) {
        if(!isComposite[i]) Prime[cnt++]=i;
        for(int j=1;j<cnt&&i*Prime[j]<MaxN;j++) {
            isComposite[i*Prime[j]]=Prime[j];
            if(i%Prime[j]==0) break;
        }
    }
}

int main(){
    LinearSieve();
    cin>>t;
    while(t--) {
        cin>>n;
        int PriCnt=0,ThePri=0,Bre=1;
        for(int i=1;i<=n;i++) {
            cin>>a[i];
            if(!isComposite[a[i]]) {
                PriCnt++;
                ThePri=a[i];
            }
        }
        if(PriCnt>=2) cout<<-1<<endl;
        else if(PriCnt==0) cout<<2<<endl;
        else {
            for(int i=1;i<=n;i++) {
                if(a[i]==ThePri) continue;
                if(a[i]%2==0) {
                    if(a[i]<2*ThePri) {
                        cout<<-1<<endl;
                        Bre=0;
                        break;
                    }
                }
                else {
                    if(a[i]-isComposite[a[i]]<2*ThePri) {
                        cout<<-1<<endl;
                        Bre=0;
                        break;
                    }
                }
            }
            if(Bre) cout<<ThePri<<endl;
        }
    }
    return 0;
}

学习总结

本专题内容主要为数论，通过学习，提高了自己的能力。

Licensed under CC BY-NC-SA 4.0
© 2025 - 2026 Dust_Li
2025寒假ACM新生线上集训
使用 Hugo 构建
主题 Stack 由 Jimmy 设计