数学问题（二）

这部分主要讲约数和同余

唯一分解定理的推论

vector<int> fac;

void solve(int n) {
    for(int i = 1; i*i <= n; i++) {
        if(n % i) continue;
        fac.push_back(i);
        if(i != n/i) fac.push_back(n/i);
    }
}

int main() {
    const int n = 100;
    solve(n);

    for(auto x : fac) printf("%d ", x);
}

把一个数分解成最接近的两个数相乘
实际上，是要找出 $\geqslant \sqrt{n}$ 的
能够被 $n$ 整除的最小的整数 $i$
$(i, n/i)$ 就是答案

pair<int, int> crack(int n) {
    int i = sqrt(n);
    int j = n / i;
    while (n % i) {
        i++;
        j = n / i;
    }

    return make_pair(i, j);
}

由此可见，一个数约数个数的上界是 $2\sqrt{n}$

求1到N每个数的正约数集合——倍数法

对每一个数 $d$，$[1, N]$ 中以 $d$ 作为约数的数

$$\{d, 2d, 3d, \cdots, \lfloor n/d \rfloor \}$$

const int maxn = 1e6 + 10;
const int N = 1e6;
vector<int> fac[maxn];

void solve(int n) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n/i; j++)
            fac[i*j].push_back(i);
    }

    for(int i = 1; i <= n; i++) {
        for(auto x : fac[i]) printf("%d ", x);
        printf("\n");
    }
}

int main() {
    solve(N);
}

算法实践

反素数

const ll inf = 0x3f3f3f3f;
const int maxn = 2*1e9 + 5;
int n;

const int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int c[11];
ll val0 = inf, cnt0 = 1;

void dfs(ll id, ll val, ll cnt) {
    if(id == 11) {
        if(cnt > cnt0 || (cnt == cnt0 && val < val0)) {
            cnt0 = cnt;
            val0 = val;
        }
        return;
    }

    ll val2 = val;
    _rep(i, 0, c[id-1]) {
        if(val2 > n) return;

        c[id] = i;
        dfs(id+1, val2, cnt*(i+1));
        val2 *= p[id];
    }
}

void init() {
    memset(c, 0, sizeof(c));
    c[0] = inf;
}


int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;
    init();
    //debug(val0);

    dfs(1, 1, 1);
    printf("%lld\n", val0);
}

取整函数的性质

Acwing199

ll n, k, ans;
ll l, r;

void init() {
    ans = n*k;
}

void solve() {
    for(l = 1; l <= n; l = r+1) {
        r = k/l == 0 ? n : min(n, k/(k/l));
        ans -= (k/l) * (r + l) * (r-l+1) / 2;
    }
    cout << ans << endl;
}

int main() {
    //freopen("input.txt", "r", stdin);
    cin >> n >> k;

    init();
    solve();
}

最大公约数

$$\forall a, b \in \mathbb{N}, \quad \textbf{gcd}(a, b) \cdot \textbf{lcm}(a, b) = a \cdot b$$

证明，$d = \text{gcd}(a, b), a_0 = a/d , b_0 = b/d$
$\text{gcd}(a_0, b_0)=1, \quad \text{lcm}(a_0, b _0) = a_0 \cdot b_0$

$\text{lcm}(a, b) = \text{lcm}(a_0\cdot d, b_0 \cdot d) = d \cdot \text{lcm}(a_0, b_0) = d \cdot a_0 \cdot b_0$
$=a \cdot b$

公约数算法

对于 $a, b$ 的任意公约数 $d$
$d|a, \ d|b \Rightarrow d \ | \ (a-b)$
$d|[a, a-b], \quad d|[b, a-b]$

$$\begin{gathered} \forall a, b \in \mathbb{N}, a \geqslant b, \textbf{gcd}(a, b) = \textbf{gcd}(a, a- b) \\ \ \\ \forall a, b \in \mathbb{N}, \textbf{gcd}(2a, 2b) = 2 \cdot \textbf{gcd}(a, b) \end{gathered}$$

Eucilid算法

$$\forall a, b \in \mathbb{N}, b \neq 0, \textbf{gcd}(a, b) = \textbf{gcd}(b, a \bmod b)$$

证明其实也比较简单
$a = q\cdot b + r$
对于任意公约数 $d$， $d|a, d|(q\cdot b)$
$\Rightarrow d | (a-qb) \Leftrightarrow d | r$
$d$ 也是 $b, r$ 的公约数，二者的公约数集合相同

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

算法实践

在 $\textbf{gcd,} \ \textbf{lcm}$ 问题中，恒等式

$$\text{lcm} = \frac{a\cdot b}{\text{gcd}}$$

是非常重要的一个理论依据

其中有一些隐含条件
$a\cdot b = G \cdot L, \quad G \leqslant L$
$G \in [\text{factors of } a]$

UVA11889
暴力做法

$$b = \frac{c \cdot \text{gcd}(a, b)}{a}$$

对 $a$ 的因子从小到大排序
我们可以暴力枚举 $a$ 的因子 $x$，让 $b=c\cdot x /a$
然后检查 $a \cdot b / \text{gcd}(a, b) = c \quad ?$

约数中的集合思想

$b = \text{gcd}(a, b) \cdot c /a$
如果 $\text{gcd}(a,b) =1, \quad b = c/a$ 就是答案

如果不呢？那么令 $b0 = c/a, \quad b = b0 * (p_1^{c_1} \cdots p_k^{c_k})$

这里有一种 过滤因子 的思想

ll A, B, C, ans;

inline ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

void solve() {
    bool fl = true;
    if(C < A || C % A) {
        fl = false;
    }

    if(!fl) {
        printf("NO SOLUTION\n");
        return;
    }

    ll B = C/A, k = 1;
    if(gcd(A, B) == 1) {
        printf("%lld\n", B);
        return;
    }

    while (gcd(A, B) > 1) {
        int d = gcd(A, B);
        k *= d;
        A /= d;
    }

    printf("%lld\n", B*k);
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        scanf("%lld%lld", &A, &C);
        init();

        solve();
    }
}

约数问题中的搜索算法

在约数问题中，常见的策略有 dfs
可以用 dfs 枚举可能的所有因子，存在 $\textbf{res}[\cdots]$ 中

Acwing200

typedef pair<int, int> PII;
const int maxn = 50000 + 10;

inline ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

ll a0, a1, b0, b1;

bool fl[maxn];
vector<int> primes;

void getPrimes(int n) {
    memset(fl, 0, sizeof(fl));
    primes.clear();
    for(int i = 2; i <= n; i++) {
        if(fl[i]) continue;
        primes.push_back(i);
        for(int j = i; j <= n/i; j++) fl[i*j] = true;
    }
}

vector<PII> fac;
void prework(ll d) {
    for(const auto& p : primes) {
        if(d % p == 0) {
            int c = 0;
            while (d % p == 0) c++, d /= p;
            fac.push_back(make_pair(p, c));
        }
    }
    if(d > 1) fac.push_back(make_pair(d, 1));
}

void dfs(ll k, ll x, vector<ll>& div) {
    if(k == fac.size()) {
        div.push_back(x);
        return;
    }

    for(int i = 0; i <= fac[k].second; i++) {
        dfs(k+1, x, div);
        x *= fac[k].first;
    }
}


void init() {
    fac.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    getPrimes(maxn);

    int kase;
    cin >> kase;

    while (kase--) {
        init();
        scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1);

        prework(b1);
        vector<ll> div;
        dfs(0, 1, div);

        ll ans = 0;
        for(auto x : div) {
            if(gcd(x, a0) == a1 && gcd(x, b0) * b1 == x * b0) ans++;
        }
        printf("%lld\n", ans);
    }
}