神秘gcd

发表于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

查询排序后的最大公约数

https://leetcode.cn/problems/sorted-gcd-pair-queries/description/

给你一个长度为 \(n(n\le10^5)\) 的整数数组 nums​，值域 \(5·10^4\) 。

两两组合出 \(n^2/2\) 个数对，对每个数对求出 gcd(nums[i], nums[j]) ，并放在一起升序排列成一个数组。

\(q(q\le10^5)\) 个查询，每次询问数组里下标为 \(q_i\) 的数是几。

点击查看题解

容斥 值域很小，可以考虑 gcd 为 \(i\) 的数对个数。如果对每个数因数分解，就可以统计出多少对数字含有因子 \(i\)，但 \(i\) 不一定是 gcd。例如，nums[i] 和 nums[j] 都有因子 \(i\)，但 gcd 可能是 \(2i,3i,4i...\)。

所以考虑容斥，先求出 \(i\) 是多少个数的因子（\(=f_i\)），即可求出 \(i\) 是多少对数的因子（\(dp_i=C_{f_i}^2\)），然后倒着循环，令 \(dp_i\gets dp_i - \sum_{k=2}dp_{ki}\)，剩下的一定就是恰好 gcd 为 \(i\) 的数对个数。

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
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define PII pair<ll,ll>

const ll inf = 1145141919810;

ll b[50005] = {};
ll dp[50005] = {};

bool cmp1(PII a,PII b) { return a.second < b.second; }
bool cmp2(PII a,PII b) { return a.first < b.first; }

class Solution {
public:
    vector<int> gcdValues(vector<int> &nums, vector<long long> &queries) {
        ll mmax = 0;
        for (ll x: nums) {
            mmax = max(mmax, x);
        }
        for (int i = 0; i <= mmax; i++)b[i] = 0;
        for (ll x: nums) {
            for (ll i = 1; i <= sqrt(x); i++) {
                if (x % i == 0) {
                    if (i * i == x)b[i]++;
                    else b[i]++, b[x / i]++;
                }
            }
        }
        for (ll i = mmax; i >= 1; i--) dp[i] = b[i] * (b[i] - 1) / 2;
        for (ll i = mmax; i >= 1; i--) {
            for (ll j = 2; i * j <= mmax; j++) {
                dp[i] -= dp[i * j];
            }
        }
        vector<int> ans;
        ll cnt = 0, index = 1;
        vector<PII > q;
        for (int i = 0; i < queries.size(); i++) {
            q.push_back({i, queries[i]});
        }
        sort(q.begin(), q.end(), cmp1);
        for (auto &[in,x]: q) {
            while (cnt <= x)cnt += dp[index++];
            x = index - 1;
        }
        sort(q.begin(), q.end(), cmp2);
        for (auto [in,x]: q)ans.push_back(x);
        return ans;
    }
};


// Solution s;
//
// int main() {
//     vector<int> a = {4, 4, 2, 1};
//     vector<ll> q = {5, 3, 1, 0};
//     s.gcdValues(a, q);
// }

子序列美丽值求和

https://leetcode.cn/problems/sum-of-beautiful-subsequences/description/

给你一个长度为 \(n(n\le10^4)\) 的整数数组 nums，值域 \(7·10^4\) 。

其所有严格上升子序列（注意，不是最长，且长度为 \(1\) 的序列也是严格上升子序列）均会对答案产生贡献，贡献值为子序列中所有数的 gcd。求答案。

点击查看题解

容斥 如果 dp，考虑前 \(i\) 个数，维护一个 set<pair<int,int>>dp[N] ，\(dp_i\) 表示以第 \(i\) 个数结尾的所有 gcd 值不同的上升子序列的 gcd 值以及个数，然后用树状数组维护其前缀和。然后对于每个 \(i\)，查询树状数组前缀 \(i-1\) 的和，来更新 \(dp_i\)。

此方法 TLE，需要更优的时间复杂度。

采用与上一题类似的容斥，则无需求复杂的前缀和，转化为容易维护的上升子序列个数，即可通过此题。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
#define lowbit(x) (x&(-x))
const ll p = 1000000007;

ll mmax = 0;
ll m, t[70005];

void add(ll x, ll k) {
    for (ll i = x; i <= m; i += lowbit(i)) {
        t[i] += k;
        t[i] %= p;
    }
}

ll search(ll x) {
    ll ans = 0;
    for (ll i = x; i > 0; i -= lowbit(i)) {
        ans += t[i];
        ans %= p;
    }
    return ans;
}

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

ll dp[70000 + 5] = {};
vector<ll> b[70005];

class Solution {
public:
    int totalBeauty(vector<int> &nums) {
        ll n = nums.size();
        mmax = 0;
        for (ll i = 0; i < n; i++) mmax = max(mmax, (ll) nums[i]);
        for (int i = 0; i <= mmax; i++)b[i].clear();
        for (ll i = 0; i < n; i++) {
            for (ll j = 1; j <= sqrt(nums[i]); j++) {
                if (nums[i] % j == 0) {
                    if (j * j == nums[i]) {
                        b[j].push_back(nums[i]);
                    } else {
                        b[j].push_back(nums[i]);
                        b[nums[i] / j].push_back(nums[i]);
                    }
                }
            }
        }
        //
        for (int i = 0; i <= mmax; i++)dp[i] = 0;
        for (ll i = 1; i <= mmax; i++) {
            //dp[i] b[i]
            m = 0;
            for (auto &x: b[i])x/=i;
            for (auto x: b[i]) m = max(m, x);
            for (int j = 0; j <= m; j++)t[j] = 0;
            for (auto x: b[i]) {
                ll cnt = search(x - 1);
                dp[i] = (dp[i] + cnt + 1) % p;
                add(x, cnt + 1);
            }
        }
        ll ans = 0;
        for (ll i = mmax; i >= 1; i--) {
            ll j = 2;
            while (j * i <= mmax) {
                dp[i] -= dp[i * j];
                dp[i] %= p;
                j++;
            }
            ans += i * dp[i];
            ans %= p;
        }
        while (ans < 0)ans += p;
        return ans;
    }
};

// Solution ss;

// int main() {
//     vector<int> a = {4, 6};
//     cout << ss.totalBeauty(a);
//     return 0;
// }

K 因数分解

https://leetcode.cn/problems/balanced-k-factor-decomposition/description/

把 \(n\) 分为 \(k\) 个数的乘积，使最大值和最小值的差值最小化。\(n\le10^5\)，\(k\leq5\)。

点击查看题解

贪心贪不了一点（

搜索与剪枝 \(k\) 很小，利用 dfs 枚举所有可能的分法，没了。

剪枝策略：

  • 由于 \(k\) 个数的顺序没有影响，可要求填的数升序排列；
  • 保持当前求得的答案比之前求出来的答案小。
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>

vector<int> d;
int ans = 1145141111;
int kk,nn;
int mind[10];

class Solution {
public:
    void dfs(int num, int k, int mmin, int mmax, vector<int> nums,int index) {
        if(mmax-mmin>ans)return;
        if (num == 0)return;
        if (k == kk) {
            mmin = min(mmin, num);
            mmax = max(mmax, num);
            nums.push_back(num);
            if (mmax - mmin < ans) {
                ans = mmax - mmin;
                for (int i = 1; i <= k; i++)mind[i] = nums[i - 1];
            }
        } else {
            for (;index<d.size();index++) {
                // if(d[index]-mmin>ans)break;
                if (num %d[index] == 0) {
                    int t1 = min(mmin,d[index]);
                    int t2 = max(mmax,d[index]);
                    nums.push_back(d[index]);
                    dfs(num /d[index], k + 1, t1, t2, nums,index);
                    nums.pop_back();
                }
            }
        }
    }

    vector<int> minDifference(int n, int k) {
        kk = k;nn=n;
        ans = 114514111;
        // memset(mind,0,sizeof)
        d.clear();
        for (int i = 1; i <= sqrt(n); i++) {
            if (n % i == 0)d.push_back(i);
        }
        dfs(n, 1, 1000000000, -1, {},0);
        vector<int> ansd;
        for (int i = 1; i <= k; i++)ansd.push_back(mind[i]);
        return ansd;
    }
};

Gellyfish and Flaming Peony

https://codeforces.com/contest/2116/problem/C

长度为 \(n\) 的数组 \(a,(n\le5000,a_i\le5000)\)。

每次可以选两个数 \(a_i,a_j\)，并把 \(a_i\) 变为 \(\gcd(a_i,a_j)\)，问最少需要多少次操作全变成相同的数。

点击查看题解

动态规划 显然这个“相同的数”是所有数的 gcd，所以先把所有数除以共同 gcd。转化为求最少多少次操作能变出第一个 \(1\)。

考虑 dp，值域比较小，dp[i][j] 表示考虑前 \(i\) 个数，\(j\) 能通过多少次操作变出来。从小到大循环 \(j\)，更新 \(\gcd(a_i,j)\)。

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<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>


int gcd(int a, int b) {
    if (b == 0)return a;
    return gcd(b, a % b);
}

void solve() {
    int n;
    cin >> n;
    int a[n + 1];
    int x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i == 1)x = a[i];
        else x = gcd(x, a[i]);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = a[i] / x;
        if (a[i] == 1)cnt++;
    }
    int dp[5005] = {};
    for (int i = 1; i <= 5000; i++)dp[i] = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 5000; j++) {
            if (dp[j] != -1) {
                int &y = dp[gcd(j, a[i])];
                if (y != -1) y = min(y, dp[j] + 1);
                else y = dp[j] + 1;
            }
        }
        dp[a[i]] = 0;
    }
    // dp[1];
    cout << dp[1] + min(n - 1, n - cnt);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << endl;
    }
    return 0;
}

求 gcd 最大

https://l.forget.where.this.problem.from/qwq

给定一个数组，对某个区间 \([l,r]\) 整体加给定数字 \(k\)，使所有数的 gcd 最大。

点击查看题解

思维题 这种做法有点乱搞，正解不是这样的，但因为 gcd 数量少，一般能过。（子序列美丽值求和就没过

dp 三个状态 \(l\) 前，\(l\sim r\)，\(r\) 后。因为前缀 gcd 的数量有限，直接用 set 暴力记录前 \(i\) 个数所有的 gcd 的可能值。

set<int> dp[n][3]，dp[i][0] 表示考虑前 \(i\) 个数，还不进行更改的所有可能 gcd 的 set，dp[i][1] 表示考虑前 \(i\) 个数，正在进行更改的所有可能 gcd 的 set，dp[i][2] 表示考虑前 \(i\) 个数，已经完成更改，\(i\) 前面的所有 gcd 的 set。

求一个正解 awa

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

//对某个[l,r]整体+k，使全部的gcd最大
//dp三个状态 l前，l~r，r后
//因为前缀gcd的数量有限，直接暴力记录下所有的gcd的可能值
int gcd(int a,int b) {
    if (b == 0)return a;
    return gcd(b, a % b);
}

set<int> dp[3]; //0 1 2
set<int> temp[3];

void solve() {
    int n, k;
    cin >> n >> k;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[0].clear();
    dp[1].clear();
    dp[2].clear();
    dp[0].insert(a[1]);
    dp[1].insert(a[1] + k);
    for (int i = 2; i <= n; i++) {
        temp[0].clear();
        temp[1].clear();
        temp[2].clear();
        for (auto c: dp[0]) {
            temp[0].insert(gcd(c, a[i]));
            temp[1].insert(gcd(c, a[i] + k));
        }
        for (auto c: dp[1]) {
            temp[1].insert(gcd(c, a[i] + k));
            temp[2].insert(gcd(c, a[i]));
        }
        for (auto c: dp[2]) {
            temp[2].insert(gcd(c, a[i]));
        }
        swap(temp, dp);
    }
    int res = 0;
    if (!dp[0].empty()) res = max(res, *dp[0].rbegin());
    if (!dp[1].empty()) res = max(res, *dp[1].rbegin());
    if (!dp[2].empty()) res = max(res, *dp[2].rbegin());
    cout << res << endl;
    return;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Maximum GCD

https://ac.nowcoder.com/acm/contest/108303/K

给定一个数组，对某个区间 \([l,r]\) 整体加某个数字 \(k\)，使所有数的 gcd 最大。

可以加无穷大，如果答案是无穷大输出 0。

点击查看题解

思维题 首先如果所有数相同，加无穷大就会使 gcd 无穷大。

由于 \(\gcd(a,b)=\gcd(a,b-a)\)，所以 \(\gcd(a_i+k,a_j+k)=\gcd(a_i-a_j,a_j+k)\)，而 \(k\) 可以任意取，于是 gcd 最大为 \(a_i-a_j\)（等价于上一题的情况，\(k=a_i-2a_j\) 在这里被给定了）。类似地，三个数的情况，gcd 最大为 \(\gcd(a_i-a_j,a_j-a_k,a_k-a_i)\)。

问题转化为上一题。

虽然可能有点乱搞，但适用范围不小。

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
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>

int gcd(int a,int b) {
    if (a == -1 || a == 0)return b;
    if (b == -1 || b == 0)return a;
    return b ? gcd(b, a % b) : a;
}


void solve() {
    int n;
    cin >> n;
    int a[n + 2];
    cin >> a[1];
    if (n == 1) {
        cout << 0;
        return;
    }
    int ans = a[1];
    for (int i = 2; i <= n; i++) {
        cin >> a[i];
        ans = gcd(ans, a[i]);
    }
    set<int> dp[3], tmp[3];
    dp[0].insert(-1);
    for (int i = 1; i <= n; i++) {
        tmp[0].clear();
        tmp[1].clear();
        tmp[2].clear();
        for (int x: dp[0]) {
            // ans = max(ans, x);
            tmp[0].insert(gcd(x, a[i]));
            tmp[1].insert(x);
        }
        for (int x: dp[1]) {
            // ans = max(ans, x);
            tmp[1].insert(gcd(x, abs(a[i] - a[i - 1])));
            tmp[2].insert(gcd(x, a[i]));
        }
        for (int x: dp[2]) {
            // ans = max(ans, x);
            tmp[2].insert(gcd(x, a[i]));
        }
        swap(dp, tmp);
    }
    int flag = 0;
    for (int x: dp[0]) {
        if (x == -1 || x == 0)flag = 1;
        ans = max(ans, x);
    }
    for (int x: dp[1]) {
        if (x == -1 || x == 0)flag = 1;
        ans = max(ans, x);
    }
    for (int x: dp[2]) {
        if (x == -1 || x == 0)flag = 1;
        ans = max(ans, x);
    }
    if (flag == 1)cout << 0;
    else cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
        cout << endl;
    }
    return 0;
}

//5 5 1 2 3 5 8 1 2 3 5 8 1 2 3 5 8 1 2 3 5 8 1 2 3 5 8

四元组

https://www.luogu.com.cn/problem/CF1107E

给出 \(n\) 和 \(k\)，要求输出 \(n\) 个四元组，每个四元组里任意两数的 gcd 为 \(k\)。要求输出的四元组内的最大数最小。

点击查看题解

思维题 很显然，对所有数除 \(k\)，题目就是要求四元组内两两互质。

由于 \(\gcd(a,b)=\gcd(a,b-a)\)，所以相邻两数互质，相邻两奇数也互质。所以连续的三个奇数、偶数、奇数两两互质。再找下一个奇数，也就是 1 2 3 5，7 8 9 11，这样以 \(6\) 为周期，同样可以推出第四个数也和前三个互质。