POJ2480:Longge’s Problem 题解

主要思路和结论

给定一个\(n\)，求\(\sum_{i=1}^{n} \gcd(i,n)\)。

题意非常的小清新，然而推式子的时候很伤心。我一开始使用打表的方法，一直没成功发现其中的规律。所以推式子的能力还是相当重要的。

我们来分析一下。对于\(i\in [1,n], gcd(i,n)=1\)，它们对答案的贡献是\(\phi(n)\)。之后来看另一部分，也就是\(j\in [1,n], gcd(j,n)=k, k \neq 1\)，我们可以除下，变成\(k*gcd(\frac{j}{k},\frac{n}{k})=k, gcd(\frac{j}{k},\frac{n}{k})=1\)，其中根据欧拉定理，有\(\phi(k)\)个这样的\(gcd\)，所以推出得\(k*\phi(k)\)。答案最后只需统计\(k\)的因数乘上\(\phi(因数)\)即可。

最后可以考虑使用 map 记录已计算过的欧拉值，可获得常数优化。

代码

// POJ2480.cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
map<ll, ll> prefix;
vector<ll> getFracted(ll x)
{
    vector<ll> res;
    for (ll i = 1; i * i <= x; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i)
                res.push_back(x / i);
        }
    return res;
}
ll phi(ll x)
{
    ll ans = x;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            ans -= ans / i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        ans -= ans / x;
    return ans;
}
int main()
{
    ll n;
    while (scanf("%lld", &n) != EOF)
    {
        ll ans = 0;
        vector<ll> container = getFracted(n);
        ll siz = container.size();
        for (int i = 0; i < siz; i++)
        {
            if (!prefix.count(n / container[i]))
                prefix[n / container[i]] = phi(n / container[i]);
            ll e = prefix[n / container[i]];
            ans += e * container[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

src:https://www.cnblogs.com/neopenx/p/4095691.html

POJ2891:Strange Way to Express Integers 题解

思路

嗯，我这种数学菜鸡来写数学题的确很难过。

首先分析题意，明显的就是提供一些线性同余方程，然后求解。但是，与中国剩余定理不同的是，这道题不保证模数互质。

\[ x \equiv a_1 (mod\ m_1) \\ x \equiv a_2 (mod\ m_2) \\ x \equiv a_3 (mod\ m_3) \\ \dots \\ x \equiv a_i (mod\ m_i) \]

但是我们仍然可以用古老的扩展欧几里得算法来解这个问题，合并方程即可。

假设我们正在解第\(k\)个方程，设\(m=\prod_{i=1}^{k-1}\)，\(x\)为满足\(1\)~\(k-1\)个方程的解。我们知道，\(tm+x\)为前\(k-1\)个方程的通解，那么我们只需要在这一轮求出\(k\)并更新答案即可，也就是解：

\[ tm_{k-1} + x_{k-1} \equiv a_k(mod\ m_k) \\ tm_{k-1} + m_k y \equiv a_k – x_{k-1}(mod\ m_k) \]

放进 \(exgcd\) 里面解下即可。

代码

// POJ2891.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 200;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y), z = x;
    x = y, y = z - (a / b) * y;
    return d;
}
int main()
{
    ll n;
    while (~scanf("%lld", &n))
    {
        ll x, y, a, b, k;
        scanf("%lld%lld", &a, &b);
        ll lcm = a, ans = b;
        bool flag = true;
        n--;
        while (n--)
        {
            scanf("%lld%lld", &a, &b);
            b = (b - ans % a + a) % a;
            ll d = exgcd(lcm, a, x, y);
            if (b % d)
                flag = false;
            else
                k = x * (b / d);
            ans += k * lcm;
            lcm = lcm / d * a;
            ans = (ans % lcm + lcm) % lcm;
        }
        if (flag)
            printf("%lld\n", ans);
        else
            puts("-1");
    }
    return 0;
}

BZOJ1257:「CQOI2007」余数之和题解

神仙思路与证明

这道题可以将式子化简为：

\[ nk-\sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor * i \]

第一部分乘积即可，第二部分直觉告诉我们\(\lfloor \frac{k}{i} \rfloor\)在一段连续的\(i\)上会相等，也就是说，是分段的。每一段的和可以直接用等差数列来求就行。我们来探究一下段区间的左右端点。我们假设目标区间是\([i,?]\)，那么这一段区间的值肯定就是\(\lfloor \frac{k}{i} \rfloor\)，反求一下那么右端点就是\( \lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor \)。可以证明右端点大于等于左端点。等差数列求和即可。

代码

// BZ1257.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k;
int main()
{
    scanf("%lld%lld", &n, &k);
    ll ans = n * k, gx;
    for (int x = 1; x <= n; x = gx + 1)
    {
        gx = (k / x) ? min(k / (k / x), n) : n;
        // x ~ gx same;
        ans -= (k / x) * (gx - x + 1) * (gx + x) / 2;
    }
    printf("%lld", ans);
    return 0;
}

OI 中的组合数学

概述
概率
- 概率相关的概念
- 概率的意义
- 同时发生的概率
- 概率的公理 & 命题
- 条件概率
  - 概念
  - 全概率公式
  - 贝叶斯公式
  - 例题
- 随机变量
- 概率在 OI 中的应用
数学期望
- 数学期望的概念
- 数学期望的线性性 & 递推
- 数学期望在 OI 中的应用

Continue reading →