简单数论杂题

DF_G · 2026-10-04 11:59:57 · 算法·理论

::::info[AI使用声明] 使用 deepseek 润色，保证人类贡献远大于 AI 贡献。 ::::

Coprime

对于一个长度为 n 的数组 a_1,a_2,\dots,a_n，我们定义：

• 两两互质，对于任意的 1\le i<j\le n 的一对 (i,j) 满足 a_i,a_j 互质（\gcd(a_i,a_j)=1）。
• 集合互质。如果 a 不满足两两互质且 \gcd\{a_1,a_2,\dots,a_n\}=1 那么称 a 数组集合互质。

如果 a 两两互质输出 pairwise coprime，如果是集合互质输出 setwise coprime，如果均不是输出 not coprime

我们设一个桶 \text{cnt}，\text{cnt}_p 表示有多少 a_i 有质因子 p。

那么我们如果要两两互质，任意的 a_i,a_j 不应该存在公共的质因数，也就是对于所有 \text{cnt}_p 都应该满足 \text{cnt}_p \le 1（最多只能有一个 a_i 有因数 p）。

然后考虑集合互质。设 \gcd\{a_1,a_2,\dots,a_n\}=x。若 x>1，取 x 的任意一个质因子 p，则 p 整除所有 a_i，即 \text{cnt}_p=n。反过来，若对某个质数 p 有 \text{cnt}_p=n，则 p 整除所有 a_i，故 p\mid x。因此 x>1 当且仅当存在质数 p 使 \text{cnt}_p=n；等价地，x=1 当且仅当对所有质数 p 都有 \text{cnt}_p\ne n。这样我们就解决了集合互质。

::::success[abc177_e]

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int V = 1e6;

int n,a[N],cnt[N];
void Get(int x){
    for(int i = 2;i * i <= x;i ++){
        if(!(x % i)) {
            while(!(x % i)) x /= i;
            cnt[i] ++;
        }
    }
    cnt[x] ++;
} 
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&a[i]);
        Get(a[i]);
    }
    int b1 = 0,b2 = 0;
    for(int i = 2;i <= V;i ++){
        if(cnt[i] > 1) b1 = 1;
        if(cnt[i] == n) b2 = 1;
    }
    if(!b1) puts("pairwise coprime");
    else if(!b2) puts("setwise coprime");
    else puts("not coprime");
    return 0;
}

::::

Orac and LCM

给定一个长度为 n 的序列 a。构造多重集 t=\{\text{lcm}\{a_i,a_j\}\mid i<j\} 求出 \gcd(t)，即计算给定序列中所有元素对的最小公倍数的最大公约数。

设 v_p(n) 表示素数 p 在 n 的质因数分解中的指数，那么得到

固定一个质数 p，设所有 a_i 中 p 的指数按从小到大排列为 e_1\le e_2\le\dots\le e_n。

对于任意一对 (i,j)，\text{lcm}(a_i,a_j) 中 p 的指数为 \max(e_i,e_j)。而最终答案的 \gcd 会对所有这些指数取最小值。

在所有 i<j 的配对中，\max(e_i,e_j) 的最小值恰好是 e_2（取 e_1 与 e_2 对应的两个下标即可得到 e_2；而任何一对 i\ne j 都有 \max(e_i,e_j)\ge \max(e_1,e_2)=e_2）。因此最小的指数 e_1 永远不会成为某个 \max 的结果（除非所有 e_i 都相等，此时 e_1=e_2，结论仍然成立），所以最终答案中 p 的指数就是第二小的指数 e_2。

注：这些所谓的最小和第二小都不是严格最小，允许第二小和最小完全相同。

::::success[CF1349A]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 +5; 
int n,a[N],cnt[N],tmp[N],ans[N];
void Get(int x){
    for(int i = 2;i * i <= x;i ++){
        int sum = 0; 
        if(!(x % i)){
            while(!(x % i)) x /= i,sum ++;
            if(sum > cnt[i]){
                ans[i] = min(ans[i],sum);
            } else {
                ans[i] = cnt[i];
                cnt[i] = sum;
            }
            tmp[i] ++;
        }
    }
    tmp[x] ++;
    int sum = 1;
    if(sum > cnt[x]){
        ans[x] = min(ans[x],sum);
    } else {
        ans[x] = cnt[x];
        cnt[x] = sum;
    }
} 
signed main(){
    scanf("%lld",&n);
    for(int i = 1;i <= N - 5;i ++) cnt[i] = 1e18,ans[i] = 1e18;
    for(int i = 1;i <= n;i ++) {
        scanf("%lld",&a[i]);
        Get(a[i]);
    }
    int anst = 1;
    for(int i = 2;i <= N - 5;i ++){
        if(tmp[i] == n) {
            for(int j = 1;j <= ans[i];j ++) anst *= i; 
        }  else if(tmp[i] == n - 1){
            for(int j = 1;j <= cnt[i];j ++) anst *= i; 
        }
    }
    printf("%lld\n",anst);
    return 0;
}

::::

Flatten

给定数组 a_1,a_2,\dots,a_n，求满足以下条件的最小的 \sum_{i=1}^n b_i：

• 对于任何满足 1\le i<j\le n 的 i,j 都满足 a_ib_i=a_jb_j。

题目给的限制条件其实就是：

那么我们考虑对于一个 b_i，其满足

那么我们可以得到，对于任意一个 b_j，它一定同时是 a_1,a_2,\dots,a_{j-1},a_{j+1},\dots,a_n 的倍数。进一步，a_jb_j 一定是 a_1,a_2,\dots,a_n 的倍数。那么 a_jb_j 的最小值就是 \text{lcm}\{a_1,a_2,\dots,a_n\}。由于 a_j 是定值，所以

::::success[abc152_e]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 5;
const int Mod = 1e9 + 7; 
int a[N],b[N],n;

int cnt[N];
void Get(int x){
    for(int i = 2;i * i <= x;i ++){
        if(!(x % i)) {
            int sum = 0;
            while(!(x % i)) x /= i,sum ++;
            cnt[i] = max(cnt[i],sum);
        }
    }
    cnt[x] = max(cnt[x],1ll);
} 
int ksm(int a,int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod; 
        b >>= 1;
    }
    return res;
}
signed main() {
    scanf("%lld",&n);
    for(int i = 1;i <= n;i ++) scanf("%lld",&a[i]),Get(a[i]);
    int L = 1;
    for(int i = 2;i <= N - 5;i ++) {
        L = (L * ksm(i,cnt[i])) % Mod;
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++) {
        b[i] = L * ksm(a[i],Mod - 2) % Mod;
        ans = (ans + b[i]) % Mod;
    }
    printf("%lld\n",ans);
    return 0;
}

::::

Two Divisors

给定 n 个数 a_1,a_2,\dots,a_n，对于每一个 a_i 找到两个约数 d_1>1 和 d_2>1，使得

\gcd(d_1+d_2,a_i)=1

或者说明不存在。

首先，我们容易证明当 a,b 互质的时候，a\times b 与 a+b 互质。 ::::info[证明]{open} 反证法。\ 假设 a\times b 与 a+b 不互质，即设

容易得到

所以我们可以得到 p\mid a 或者 p\mid b。\ 当 p\mid a 的时候，由于 p\mid(a+b)，所以 p\mid b。所以 \gcd(a,b)\ge p>1，与 a,b 互质的条件相背。p\mid b 同理。\ 所以 a\times b 与 a+b 在 a,b 互质的情况下互质。 ::::

我们设 a_i=p_1^{e_1}p_2^{e_2}\dots p_d^{e_d}（其中 p 数组互不相等），设 d_1=p_1^{e_1}，d_2=\frac{a_i}{p_1^{e_1}}，此时 d_1 与 d_2 互质，于是 d_1+d_2 与 d_1\times d_2=a_i 互质，满足条件。\ 注意上面假设 d\ge 2，但是事实上可能有 d\le 1，此时由于凑不出来上面的情况（要求 d_1,d_2>1）所以无解\ 但是直接找质因数无疑是超时的。那么我们埃氏筛（也可以是别的筛）出最小的质因数即可。

::::success[CF1366D]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 5;
const int M = 1e7 + 5;
int n;
int a[N],ans[N],tmp[N],d1[N],d2[N],at[N];
int spf[M];

void init() {
    for(int i = 2;i <= M - 5;i ++) {
        if(spf[i]) continue;
        spf[i] = i;
        if(i * i > M - 5) continue;
        for(int j = i * i;j <= M - 5;j += i){
            spf[j] = (spf[j] ? spf[j] : i);
        }
    }
} 

signed main() {
    init();
    scanf("%lld",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%lld",&a[i]);
        int x = a[i];
        d1[i] = 1; 
        while(!(x % spf[a[i]])) x /= spf[a[i]],d1[i] *= spf[a[i]];
        d2[i] = a[i] / d1[i];
        if(d2[i] == 1){
            d1[i] = d2[i] = -1;
        }
    }
    for(int i = 1;i <= n;i ++) printf("%lld ",d1[i]);
    puts("");
    for(int i = 1;i <= n;i ++) printf("%lld ",d2[i]);
    return 0;
} 

::::

素数密度

给定 L,R，计算 [L,R] 中质数的个数（1\le L\le R<2^{31},R-L\le 10^6）

直接线性筛时间复杂度是 O(R) 的，并且空间也吃不消。\ 由于我们知道任意一个合数 x=a\times b，那么 \min\{a,b\}\le \sqrt{x}。由于我们的线性筛是让一个数被他的最小质因数筛掉，所以实际上我们可以把线性筛分成两步：

• 先筛 [1,\sqrt{R}] 确保后面的合数都能被他的最小质因子筛掉。
• 然后筛 [L,R] 计算答案。但是如果直接开静态数组会爆炸，所以需要把中间没有用的 (\sqrt{R},L) 的内存分给后面的值来节省空间。

这样的话时间复杂度就是 O(\sqrt{R}+R-L+1)。

::::success[P1835]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int M = 1e7 + 5;
int l,r,ans,txk;
int spf[M];

void init(int tx) {
    for(int i = 2;i <= tx;i ++) {
        if(spf[i]) continue;
        spf[i] = i;
        for(int j = i * i;j <= tx;j += i) if(!spf[j]) spf[j] = i;
    }

    for(int p = 2;p <= tx;p ++) {
        if(spf[p] != p) continue;
        int st = max(p * p,(l + p - 1) / p * p);
        for(int j = st;j <= r;j += p) {
            if(!spf[j + txk]) spf[j + txk] = p;
        }                         
    }
}

signed main() {
    scanf("%lld%lld",&l,&r);
    int tx = sqrt(r);
    while((tx + 1) * (tx + 1) <= r) tx ++;
    while(tx * tx > r) tx --;

    txk = tx + 1 - l;
    init(tx);

    ans = 0;
    for(int i = l;i <= r;i ++) {
        if(i == 1) continue;
        if(!spf[i + txk]) ans ++;
    }
    printf("%lld\n",ans);
    return 0;
}

::::

Sum of gcd of Tuples

对于所有的满足 1\le a_i\le k 的长度为 n 的序列 \{a_1,a_2,\dots,a_n\}，计算所有的 n^k 种排列方式的 \gcd\{a_1,a_2,\dots,a_n\} 的和。

我们首先发现，对于一种满足 x\mid\gcd\{a_1,a_2,\dots,a_n\} 的数对，x 会贡献 x\times (\lfloor \frac{k}{x} \rfloor)^n。 ::::info[为什么]{open} 因为我们考虑在满足条件的 a 数组集体 a\to \frac{a}{x} 剩余的值都在值域 [1,\lfloor \frac{k}{x} \rfloor] 排列的方案数是 (\lfloor \frac{k}{x} \rfloor)^n，一种序列贡献 x，所以就是 x\times (\lfloor \frac{k}{x} \rfloor)^n。 :::: 这些序列的实际 \gcd 不一定是 x，而是 x 的某个倍数。所以这样做会有重复。\ 我们需要调整权重为 w(x)，使得对于任意实际 \gcd=g 的序列被所有 x\mid g 的项统计之后总权重恰好是 g，也就是

由莫比乌斯反演可知，满足该式的函数 w 唯一，即欧拉函数 \varphi(x)。

所以最后的答案就是

::::info[什么是欧拉函数？]{open} 欧拉函数 \varphi(n) 表示 1\sim n 中与 n 互质的正整数个数。对于质数的幂，若 p 为质数，则

因为在 1\sim p^k 中，只有 p 的倍数不和 p^k 互质，这样的数有 p^{k-1} 个。\ 欧拉函数是积性函数，即

通项公式

结论：若 n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} 那么有

证明：容斥原理。一个数 x 与 n 不互质，当且仅当它被 n 的某个质因子 p_i 整除。设 A_i=\{x\in[1,n]:p_i\mid x\} 那么我们可以得到

依靠容斥原理进行展开：

而 A_i 就是 p_i 的倍数，A_i\cap A_j 就是 p_ip_j 的倍数以此类推

那么我们可以得到

提出 n 之后第一项后面的项恰好是 \prod_{i=1}^k\left(1-\frac{1}{p_i}\right) 的展开式，可以得到

因子和恒等式

结论：

证明：令 S=\{1,2,\dots,n\}。对于每一个 k\in S，将分数 \frac{k}{n} 化为最简分数，设约分后为最简分数 \frac{a}{d}，那么有

反过来，给定满足上述条件的数对 (a,d)，取 k=\frac{a\times n}{d}，则 1\le k\le n 且 \frac{k}{n} 约分后恰为 \frac{a}{d}。于是 k\in S 与满足上述条件的数对 (a,d) 之间建立了一一对应。

把所有 n 个分数按约分后的分母分类：

• 分母为 d 的分数有 \varphi(d) 个（因为 a 与 d 互质且 1\le a\le d）；不同的 d 对应的分数互不重叠，因为一个分数约分后的分母是唯一的。
• 所有 d\mid n 的这些组恰好覆盖了全部 n 个分数。

因此，分数的总数等于各组个数之和：

::::success[abc162_e]

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
const int Mod = 1e9 + 7; 
int n,k,ans=0,phi[N];

int ksm(int a,int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod; 
        b >>= 1;
    }
    return res;
}
void init() {
    for(int i = 1;i <= k;i ++) phi[i] = i;
    for(int i = 2;i <= k;i ++) {
        if(phi[i] == i) {
            for(int j = i;j <= k;j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
}
signed main() {
    scanf("%lld%lld",&n,&k);
    init();
    for(int i = 1;i <= k;i ++){
        ans = (ans + phi[i] * ksm(k / i,n) % Mod) % Mod; 
    }
    printf("%lld\n",ans);
    return 0;
}

::::

Divide Both

找到满足下列条件的整数对 (x,y) 的数量：

我们分为两个部分，先统计所有不互质的有序对记作 A，然后从 A 中扣除成倍数关系的有序对。\ 我们设 c_d 是区间 [L,R] 中 d 的倍数个数，那么

那么 c_d^2 就是两个数都被 d 整除的有序对的个数。设 f(d) 为恰好 \gcd(x,y)=d 的有序对个数。由于直接用 c_d^2 会重复，因为它包含了 \gcd 是 d 的倍数的数对，需要减去倍数，可以容斥

倒序即可。\ 根据定义，我们不难得到 A=\sum_{d=2}^R f(d)。\ 我们只需要考虑所有 d\in [\max(L,2),R] ::::info[理由]{open}