P2398 GCD SUM

题意:

求

$$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$$

思路:

• $30pts$ - 暴力枚举 - $O(n^2logn)$
• $100pts$ - 考虑枚举$gcd(i,j) = k$ - $O(n)$
  对于$\forall$$gcd(i,j)=1$，有$gcd(i*k,j*k)=k$
  而$gcd(1,1)=1$我们不能重复计算，所以$gcd(i,j)=k$的个数为:

$$2*\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor } \varphi (i)-1 $$

本题枚举$i:1\to$ $n$累计$k$的贡献即可，可以使用前缀和优化区间查询

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 5;
int n, ans;
int pri[N], tot;
int phi[N], sum[N];
bitset<N> p;
inline void getPrimes(int lim)
{
    p.set();
    p[0] = p[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
            pri[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * pri[j] <= lim; j++)
        {
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else
                phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    getPrimes(n);
    for (int i = 1; i <= n; i++)
        ans += (sum[n / i] * 2 - 1) * i;
    cout << ans << endl;
}

P1287 盒子与球

显然就是 $S(n,r)\times A_r^r$。（$S(n,r)$ 为第二类斯特林数）

#include <bits/stdc++.h>
using namespace std;
long long n, k;
long long S[15][15]; // 第二类斯特林数
long long fact[15];  // i!
int main()
{
    cin >> n >> k;
    fact[0] = 1;
    for (int i = 1; i <= k; i++)
        fact[i] = fact[i - 1] * i;
    // 处理第二类斯特林数
    S[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        S[i][0] = 0;
        for (int j = 1; j <= i; j++)
            S[i][j] = S[i - 1][j - 1] + j * S[i - 1][j];
    }
    cout << S[n][k] * fact[k] << "\n";
    return 0;
}

P2567 [SCOI2010]幸运数字

#include <bits/stdc++.h>
using namespace std;
long long a, b, ans;
bool cmp(long long a, long long b)
{
    return a > b;
}
//生成所有 10 位以内的幸运数字
int totLt, totL;
long long Lt[3005];
long long L[3005];
void dfsL(int x, long long num)
{
    if (num > 0)
        Lt[++totLt] = num;
    if (x == 11)
        return;
    dfsL(x + 1, num * 10 + 6);
    dfsL(x + 1, num * 10 + 8);
}
//容斥
long long gcd(long long a, long long b)
{
    return b ? gcd(b, a % b) : a;
}
long long lcm(long long a, long long b)
{
    return a / gcd(a, b) * b;
}
void dfs(int x, int cnt, long long now)
{
    if (now > b)
        return;
    if (x > totL)
    {
        if (cnt % 2 == 1)
            ans += b / now - (a - 1) / now;
        else
            ans -= b / now - (a - 1) / now;
        return;
    }
    if (1.0 * now / gcd(now, L[x]) * L[x] <= b)
        dfs(x + 1, cnt + 1, lcm(now, L[x]));
    dfs(x + 1, cnt, now);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //预处理所有幸运数字，删除倍数中较大的
    dfsL(1, 0);
    sort(Lt + 1, Lt + totLt + 1, cmp);
    for (int i = 1; i <= totLt; i++)
    {
        bool flag = true;
        for (int j = i + 1; j <= totLt; j++)
            if (Lt[i] % Lt[j] == 0)
            {
                flag = false;
                break;
            }
        if (flag)
            L[++totL] = Lt[i];
    }
    //输出 [a,b] 内的所有 L 的倍数数量
    cin >> a >> b;
    ans = 0;
    //下面的for循环也可以改成 dfs(1,0,1)，然后在dfs中只有cnt>0时才统计答案即可。
    for (int i = 1; i <= totL; i++)
        dfs(i + 1, 1, L[i]);
    cout << ans << endl;
    return 0;
}

P5520 [yLOI2019] 青原樱

先拿出 $(m-1)$ 个空，把树苗无限制放好后，每两棵树苗间放一个空即可满足限制。

$C_{n-(m-1)}^m$ 选出 $m$ 个位置方树，树的放法有 $A_m^m$ 种，所以答案就是：

$$C_{n-(m-1)}^m \times A_m^m = A_{n-(m-1)}^m$$

#include <bits/stdc++.h>
using namespace std;
long long type, n, m, p;
int main()
{
    cin >> type >> n >> m >> p;
    // A(n-(m-1), m)
    long long x = n - (m - 1);
    long long y = m;
    long long ans = 1;
    for (int i = x; i >= x - y + 1; i--)
        ans = (ans * i) % p;
    cout << ans << "\n";
    return 0;
}

P3197 [HNOI2008]越狱

吵架的方案正面求解比较难，考虑正难则反。

• 总方案：$m^n$。
• 不吵架的方案：$m\times (m-1)^{n-1}$。第一个房间宗教随意，后面每个都不能和前面相同。

#include <bits/stdc++.h>
#define int long long
using namespace std;
// a^b (mod p)
long long quick_pow(long long a, long long b, long long p)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % p;
        b = b >> 1;
        a = (a * a) % p;
    }
    return res;
}
int n, m, mod;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    mod = 100003;
    cin >> m >> n;
    int all = quick_pow(m, n, mod);
    int sub = m * quick_pow(m - 1, n - 1, mod) % mod;
    cout << (all - sub + mod) % mod << "\n";
    return 0;
}