「CF1295」Same GCDs

Summarize

给定正整数 $a$，$m$（$a<m$）。计算符合条件的 $x\in[0,m)$ 的个数，使得 $\text{gcd}(a,m)=\text{gcd}(a+x,m)$。

$a\le 1e10,m\le 1e10$

Solution 1

记 $a+x=y$。题目即为求复合条件的 $y\in[a,a+m)$ 使得 $\text{gcd}(a,m)=\text{gcd}(y,m)$。记 $\text{gcd}(a,m)=g$。可以发现，$y$ 可以表示为 $kg$，其中 $k$ 的取值范围为 $[l,r],l=\lceil\frac{a}{g}\rceil,r=\lceil\frac{a+m}{g}\rceil-1$。观察到 $\text{gcd}(kg,m)=g$，即 $\text{gcd}(k,m/g)=1$，$k$ 与 $m/g$ 互质。记 $\texttt{solve(n,m)}$ 函数为 $1-n$ 的整数中与 $m$ 互质的数的个数，则本题答案为 $\texttt{solve(r,m/g)-solve(l-1,m/g)}$。

接下来考虑 $\texttt{solve()}$ 函数的设计。注意到一个 $1e10$ 级别的数最多只有 10 个质因子，因此可以使用状态压缩和容斥原理计算出 $1-n$ 中与 $m$ 不互质的数的个数。

Solution 2

有 $\text{gcd}((a+x)%m,m)=\text{gcd}(a,m)$。注意到当 $x\in[0,m)$ 时，$(a+x)%m$ 的值取遍 $[0,m)$。换言之，我们只需计算符合条件的 $y\in[0,m)$ 使得 $\text{gcd}(y,m)=gcd(a,m)$。记 $\text{gcd}(a,m)=g$，即 $\text{gcd}(y/g,m/g)=1$，即 $\varphi(m/g)$。计算欧拉函数即可。

Note

不能感性理解！要把式子推出来

Code 1

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a > b ? b : a)
typedef long long ll;
void readint() {}
template <class T1, class... T2>
void readint(T1 &i, T2 &... rest) {
    i = 0;
    char c;
    bool f = false;
    while (!isdigit(c = getchar())) f = c == '-';
    do
        i = (i << 3) + (i << 1) + c - '0';
    while (isdigit(c = getchar()));
    if (f)
        i = -i;
    readint(rest...);
}
using namespace std;

ll solve(ll n, ll m) {
    vector<ll> p;
    for (ll i = 2; i * i <= m; ++i) {
        if (m % i == 0) {
            p.push_back(i);
            while (m % i == 0) m /= i;
        }
    }
    if (m > 1) p.push_back(m);
    ll ret = 0;
    for (ll s = 1; s < (1 << p.size()); ++s) {
        ll mult = 1, bits = 0;
        for (int i = 0; i < p.size(); ++i) {
            if (s & (1ll << i)) {
                bits++;
                mult *= p[i];
            }
        }
        ll cur = n / mult;
        if (bits & 1) ret += cur;
        else ret -= cur;
    }
    return n - ret;
}

int T;

int main() {
    readint(T);
    while (T--) {
        ll a, m;
        readint(a, m);
        ll g = __gcd(a, m);
        ll l = a / g + (a % g != 0), r = (a + m) / g - ((a + m) % g == 0);
        printf("%I64d\n", solve(r, m / g) - solve(l - 1, m / g));
    }
    return 0;
}

Code 2

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

int T;

ll phi(ll n) {
    ll ret = n;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) ret = ret / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) ret = ret / n * (n - 1);
    return ret;
}

int main() {
    cin >> T;
    while (T--) {
        ll a, m;
        cin >> a >> m;
        ll g = __gcd(a, m);
        cout << phi(m / g) << endl;
    }
    return 0;
}

# 容斥原理, 数学, 数论, 欧拉函数, 状态压缩

「CF1295」Same GCDs

Summarize

Solution 1

Solution 2

Note

Code 1

Code 2

Comments

一言（ヒトコト）

Recent

Categories

Tag Cloud

Your browser is out-of-date!