[Fortuna OJ]Aug 10th – Group A 解题报告

A – 数学题

这道题二次函数的暴力分有 60 分,正解来自于论文。

这道题的主要是利用了一个结论,并且运用了辗转相除法的一种思想来对问题进行化简。首先,我们把向量调整至同向,且使\(|\vec{a}| < |\vec{b}|\),然后再来推导一个结论:

结论   对于\(\vec{a}, \vec{b}\),如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\),那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。

这个结论的证明参见《欧几里得算法的应用》。所以,我们就可以大概知道,我们可以将较长的向量分解:\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道,这道题可以笑掉这个\(k \vec{a}\),所以就可以用辗转相除法的套路进行处理。具体见代码:

继续阅读[Fortuna OJ]Aug 10th – Group A 解题报告

[Fortuna OJ]Jul 8th – Group B 解题报告

今天这几题咋就那么毒瘤呢?

A – String

其实这道题考场上应该能做出来的,是一道很简单的计数问题。在考场上一看到字符串就懵了,不知道为什么我对字符串的字典序有阴影,现在看来就是一道傻逼题。

考虑这样计数:

  1. 枚举一个\(i\),考虑前\(i-1\)个字符与\(T\)串相同,然后第\(i\)个字符小于\(T[i]\),这样可以保证后面怎么放置字母都能满足要求。
  2. 在枚举了\(i\)的情况下,枚举字符\(ch\),范围在\([a, T[i])\),考虑以下两种情况对答案的贡献:
    1. 如果\(ch = S[i]\),那么后面需要变动的字符个数为\(k\)个,对答案的贡献:\[ {n – i \choose k} 25^{k} \]
    2. 如果不等于,那么后面需要变动的字符个数为\(k-1\)个,因为本位占了一个;对答案的贡献:\[ {n – i \choose k – 1} 25^{k – 1} \]
  3. 贡献之后,如果本位\(T[i] \neq S[i]\),那么把\(k–\),代表多固定了一个不同的字符。

继续阅读[Fortuna OJ]Jul 8th – Group B 解题报告

BZOJ1101:[POI2007]Zap 题解

主要思路

这道题是一道很好的题,包含了数论里面的很多技巧。

首先,这是一道多组询问的题,询问数量非常的大,遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞,开始从这方面分析。

复习一下莫比乌斯函数的定义:

\[ \mu(x) = \begin{cases} 0, 在x中存在指数大于一的质因子 \\ 1, 在x中质因子指数都为1且质因子个数为偶数 \\ -1, 在x中质因子质数都为1且质因子个数为奇数 \end{cases} \]

我们观察一下答案式子:\(\sum_{i,j} [gcd(x,y)=d]\)。我们先把\(gcd\)部分进行变换:

\[gcd(\frac{x}{d}, \frac{y}{d}) = 1\]

显然,这样的对数为\( \lfloor \frac{x}{d} \rfloor*\lfloor \frac{y}{d} \rfloor \)。我们考虑容斥:因为如果暴力累加的话,会多出很多不该存在的部分,比如说又是2的倍数又是3的倍数的部分。

所以最后答案式为:

\[\sum_{i=1}^{min\{a,b\}} \mu(i)*\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor \]

这时有个技巧,我们可以证明在整数段\([x, min\{ \lfloor \frac{a}{\lfloor \frac{a}{x} \rfloor} \rfloor, \lfloor \frac{b}{\lfloor \frac{b}{x} \rfloor} \rfloor \} ]\)上,\(\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor\)的结果是一样的,直接前缀和与之相乘即可。最后这样的段最坏情况为\(O(\sqrt{a}+\sqrt{b})\),所以时间复杂度比较低。

代码

// BZ1101.cpp
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int MAX_N = 5e4 + 200;
ll mobi[MAX_N], sum[MAX_N], n;
bool vis[MAX_N];
int main()
{
    for (int i = 1; i < MAX_N; i++)
        mobi[i] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (vis[i])
            continue;
        mobi[i] = -1;
        for (int j = 2; i * j < MAX_N; j++)
        {
            vis[i * j] = true;
            if (j % i == 0)
                mobi[i * j] = 0;
            else
                mobi[i * j] *= -1;
        }
    }
    for (int i = 1; i < MAX_N; i++)
        sum[i] = sum[i - 1] + mobi[i];
    scanf("%d", &n);
    while (n--)
    {
        int a, b, k, gx;
        scanf("%d%d%d", &a, &b, &k);
        a /= k, b /= k;
        int ans = 0;
        for (int i = 1; i <= min(a, b); i = gx + 1)
        {
            gx = min(a / (a / i), b / (b / i));
            ans += (sum[gx] - sum[i - 1]) * (a / i) * (b / i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ2818:GCD 题解

思路

乍一看其实可以跟欧拉函数扯上关系。我们要求的是\(gcd(x,y) \in Prime, x, y \leq N\)的有序对个数。我们设那个质数为\(s\),则可以化为:

\[ x = sa, y = sb \\ gcd(a, b) = 1 \]

嗯,看到欧拉函数的影子了。对于每一个质数\(s\),它对答案的贡献是:

\[ 2 * \sum_{ 1 \leq i \leq \lfloor \frac{n}{s} \rfloor } \phi(i) – 1 \]

我来解释一下:因为\(x,y \leq n\),所以\(sa \leq n\),\(sb \leq n\),得:

\[ a,b \leq \frac{n}{s} \]

所以会有这么多对,考虑这个是有序对,所以乘上二,再删除掉\((i,i)\)这样的有序对重复即可得到答案。注意,可以用前缀和欧拉函数值来进行优化。

代码

// BZ2818.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 10000005;
ll n, phi[MAX_N];
bool isPrime[MAX_N];
int main()
{
    //memset(isPrime, true, sizeof(isPrime));
    scanf("%lld", &n);
    for (int i = 2; i <= n; i++)
        phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (!isPrime[i])
            for (int j = i; j <= n; j += i)
            {
                if (j != i)
                    isPrime[j] = true;
                phi[j] = phi[j] / i * (i - 1);
            }
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] += phi[i - 1];
    long long ans = 0;
    for (int i = 2; i <= n; i++)
        if (!isPrime[i])
            ans += 2 * phi[n / i] - 1;
    printf("%lld", ans);
    return 0;
}

P1072:Hankson 的趣味题题解

超级简洁的做法

看到这篇题解之后立马 A 掉了,真的很简洁的一个做法。

我们有\(gcd(x,a_0)=a_1\),根据结论\(gcd(a,b)=c \to gcd(\frac{a}{c},\frac{b}{c})=1\),可以推出:

\[gcd(\frac{x}{a_1},\frac{a_0}{a_1})\]

另一个式子\(lcm(x,b_0)=b_1\)可以转换为:

\[ lcm(x,b_0)=b_1 \\ gcd(x,b_0)*lcm(x,b_0)=xb_0 \\ gcd(x,b_0)=\frac{xb_0}{b_1} \\ gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1 \]

可以看出,\(x\)为\(b_1\)的一个约数,\(a_1\)是\(x\)的一个约束,根据这两个条件和两个\(gcd\)条件,进行枚举即可。

代码

// CH3201.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a0, a1, b0, b1;
int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int ans = 0;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        int p = b1 / b0, q = a0 / a1;
        for (int x = 1; x * x <= b1; x++)
            if (b1 % x == 0)
            {
                if (x % a1 == 0 && gcd(p, b1 / x) == 1 && gcd(q, x / a1) == 1)
                    ans++;
                int y = b1 / x;
                if (x == y)
                    continue;
                if (y % a1 == 0 && gcd(p, b1 / y) == 1 && gcd(q, y / a1) == 1)
                    ans++;
            }
        printf("%d\n", ans);
    }
    return 0;
}