Gauss's blog

Gauss's blog

I’d go back to December turn around and make it alright.

题解 [十二省联考2019] 骗分过样例

posted on 2021-07-07 07:48:18 | under 数论 |

笔者写这篇题解主要有以下原因

  • 第一篇题解给的模数有误

  • 许多题解对原根及其性质讲解不清,容易给学习者以误导或使其感到迷惑.


Case 1~Case 3

由功能编号和数据不难看出题目要求 $19^x$ 对 $998244353$ 取模的值.

当 $x$ 较小时,线性乘;

当 $x$ 较大但还在 long long 范围以内时,使用快速幂;

当 $x$ 特别大以至于任何数据类型都存不下时,用快速读入加欧拉定理.

Case 4

software4.ans 打开,输出其中最大的数.

发现它跟一个很臭的数很像!

在这个数后面分别添加 $1,3,7,9$,判断其是否为质数且符合题目要求......

最终发现题目要求 $19^x$ 对 $1145141$ 取模的值.

Case 5

software5.insoftware5.ans 都打开,并按照指数从小到大排序.

假设我们已经知道 $a\equiv 19^x\pmod{p},b\equiv 19^y\pmod{p},c\equiv 19^{x-y}\pmod{p}(x>y)$.

由于 $19^{x}-19^y-19^{x-y}(19^y-1)\equiv 0\pmod{p}$,故有 $p|(a-b-c(b-1))$.

将所有合法的 $a,b,c$ 三元组找出,求 $a-b-c(b-1)$ 的 gcd 即可.

Case 6~7

由功能编号,数据和 Hint 可综合判断出,题目要求的是 $19^x$ 边乘边模 $998244353$ 边爆 int 的值.

当 $x$ 较小时,可以模拟自然溢出;

当 $x$ 较大时,寻找循环节并用 hash 表存储即可.

Case 8~10

由数据和功能编号可以判断出,题目要求询问一个区间中的每个数是否为质数.

当区间的右端点较小时,可以用欧拉筛;

否则上 Miller_Rabin,实测基数仅需选取 $2$ 和 $3$.

Case 11~13

由数据和功能编号可以判断出,题目要求询问一个区间中的每个数的 Mobius 函数值.

首先可以考虑将 $\sqrt{r}$ 以内的质数筛出来,再贡献到它们在给定区间中的倍数.

但是注意到 $r$ 在 Case 13 中达到了 $10^{18}$,所以要考虑优化.

实际上,如果我们仅筛出 $10^7$ 内的质数,再用上述方法,最终只会有两万多个数答案有误,这个完全可以打表打出来.

或者,分别考虑每个数被除以后是否为完全平方数、质数异或是两个不同的质数之乘积,判断质数仍然用 Miller_Rabin 算法.

这里有几个卡常技巧:

  1. 用质数除它们的倍数的时候不要直接除,而是将每个数的所有质因子乘起来,最后一起除.

  2. Miller_Rabin 选取两个基数还是太慢了,找1个合适的基数即可.

Case 14~16

有数据和功能编号可以判断出,题目要求询问一个区间中的每一个数是否为给定质数的原根.

这里补充原根的定义及一些对题目有用的性质.

下文提到的 $a,n$ 均满足 $(a,n)=1,a\ne 0,n>0$.

称 $a^x\equiv 1\pmod{n}$ 的最小正整数解为 $a$ 模 $n$ 的阶,记为 $\text{ord}_n a$.

性质1.1

$a^x\equiv 1\pmod{n}$ 当且仅当 $\text{ord}_n a|x$.

推论:$\text{ord}_na|\varphi(n)$.

证明略.

性质1.2

$a^i\equiv a^j\pmod{n}$ 当且仅当 $i\equiv j\pmod{\text{ord}_n a}$.

证明略.

原根

若 $\text{ord}_na=\varphi(n)$,则称 $a$ 为 $n$ 的一个原根.

性质2.1

若 $r$ 为 $n$ 的一个原根,则 $r^1,r^2,\cdots,r^{\varphi(n)}$ 两两模 $n$ 不同余且与 $n$ 互质.

证明:

先证两两模 $n$ 不同余,若 $r^i\equiv r^j\pmod{n},1\le i,j\le \varphi(n)$,则 $i\equiv j\pmod{\text{ord}_n r}$,因为 $r$ 是 $n$ 的原根,所以 $\text{ord}_nr=\varphi(n)$,即 $i\equiv j\pmod{\varphi(n)}$,从而 $i=j$,即证 $r^i$ 两两模 $n$ 不同余.

而由 $(r,n)=1$ 立即得到 $(r^i,n)=1$.

证毕.

性质2.2

若 $\text{ord}_na=t$,则 $\text{ord}_n(a^u)=t/(t,u)$.

证明:

设 $s=\text{ord}_n(a^u)$;

再设 $v=(t,u),t=t_1v,u=u_1v$,则有 $(t_1,u_1)=1$;

一方面,$\displaystyle(a^u)^{t_1}=(a^t)^{u_1}\equiv 1\pmod{n}$,故 $s|t_1$;

另一方面,$(a^u)^s=a^{us}\equiv 1\pmod{n}$,故 $t|us$,即 $t_1|v_1s$,考虑到 $(t_1,v_1)=1$,从而 $t_1|s$.

综上,$s=t_1=t/(t,u)$,证毕.

推论:若 $a$ 是 $n$ 的原根,则 $a^x$ 是 $n$ 的原根当且仅当 $(x,\varphi(n))=1$.

于是我们得到了一个解决本题的方法:

从输出中找出 $p$ 一个原根 $g$.

由于所有与 $p$ 互质的数都可以表示为 $g^x$,所以我们将 $x$ 从 $1$ 到 $p-1$ 扫一遍,将区间中的数标记出来,没被标记到的数必定不是 $p$ 的原根.

再求出 $p-1$ 的所有质因子,筛出这些质数的倍数,没有被筛去的指数 $x$ 所对应的 $g^x$ 即为 $n$ 的原根.

对于最后一个点,按照提示枚举质数,找到符合数据的即可.

Code

不长,就 6.6k.

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
*/
#include <cstdio>
#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <cstdlib>

using namespace std;
typedef unsigned long long ull;
const ull mod1 = 998244353;
const ull mod2 = 1145141;
const ull mod3 = 5211600617818708273;
const int P = 13123111;
const int N = 1e7;
int n, table[2500000];
char type[20];
int tot, prime[N / 10 + 1], mu[N + 1], fac[N / 100 + 1], _log[P + 1];
bool check[N + 1], vis[P + 1];
long long id[N / 10 + 1];
map<int, int> hash;

ull pow(ull a, ull b, ull mod)
{
    ull ans = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1) ans = ans * a % mod;
    return ans;
}
ull mul(ull a, ull b, ull mod)
{
    ull ans = 0;
    for(; b; b >>= 1, a = (a + a) % mod)
        if(b & 1) ans = (ans + a) % mod;
    return ans; 
}
ull _pow(ull a, ull b, ull mod)
{
    ull ans = 1;
    for(; b; b >>= 1, a = mul(a, a, mod))
        if(b & 1) ans = mul(ans, a, mod);
    return ans;
}
/*-----------------------------------------------------------*/
long long _mul(long long a, long long b, long long mod)
{
    a %= mod, b %= mod;
    long long z = (long double)a * b / mod;
    z = a * b - z * mod;
    return (z + mod) % mod;
}
long long __pow(long long a, long long b, long long mod)
{
    long long ans = 1;
    for(; b; b >>= 1, a = _mul(a, a, mod))
        if(b & 1) ans = _mul(ans, a, mod);
    return ans;
}
bool Miller_Rabin(long long n, int v = 0)
{
    if(n == 2 || n == 3) return 1;
    if(!(n & 1)) return 0;
    long long m = n - 1, q = 0;
    for(; !(m & 1); m >>= 1)
        q++;
    for(long long a = 2; a <= 3 - v; a++)
    {
        long long x = __pow(a, m, n), y;
        for(int k = 0; k <= q; k++)
        {
            y = _mul(x, x, n);
            if(y == 1 && x != 1 && x != n - 1)
                return 0;
            x = y;
        }
        if(y != 1) return 0;
    }
    return 1;
}
/*----------------------------------------------------------*/
bool __check(int g)
{
    for(int i = 1; i <= fac[0]; i++)
    {
        if(pow(g, fac[i], 998244353) == 1)
            return 0;
    }
    return 1;
}
bool _check(int g, int p)
{
    for(int i = 1; i <= fac[0]; i++)
    {
        if(pow(g, fac[i], p) == 1)
            return 0;
    }
    return 1;
}
void seive()
{
    for(int i = 2; i <= N; i++)
    {
        if(!check[i]) prime[++tot] = i;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++)
        {
            check[i * prime[j]] = 1;
            if(i % prime[j] == 0)
                break;  
        }
    }
}
int main()
{
    freopen("software.in", "r", stdin);
    freopen("software.out", "w", stdout);
    scanf("%s", type);
    if(type[0] == '1' && type[1] == '_')
    {
        scanf("%d", &n);
        for(; n--; )
        {
            ull a = 0;
            char ch;
            for(; !isdigit(ch = getchar()); );
            for(; isdigit(ch); a = ((a << 1) + (a << 3) + (ch ^ 48)) % (mod1 - 1), ch = getchar());
            printf("%llu\n", pow(19, a, mod1));
        }
    }
    else if(type[0] == '1' && type[1] == '?' && type[2] == '+')
    {
        scanf("%d", &n);
        for(; n--; )
        {
            ull a;
            scanf("%llu", &a);
            printf("%llu\n", _pow(19, a, mod3));
        }
    }
    else if(type[0] == '1' && type[1] == '?')
    {
        scanf("%d", &n);
        for(; n--; )
        {
            ull a = 0;
            char ch;
            for(; !isdigit(ch = getchar()); );
            for(; isdigit(ch); a = ((a << 1) + (a << 3) + (ch ^ 48)) % (mod2 - 1), ch = getchar());
            printf("%llu\n", pow(19, a, mod2));
        }
    }
    else if(type[0] == '1' && type[1] == 'w')
    {
        scanf("%d", &n);
        int ans = 1;
        int st, len;
        for(int i = 1; ; i++)
        {
            ans = ans * 19 % 998244353;
            if(!hash.count(ans))
                hash[ans] = i;
            else
            {
                st = hash[ans], len = i - st;
                break;
            }
            table[i] = ans;
        }
        for(; n--; )
        {
            long long a;
            scanf("%lld", &a);
            if(!a)
                puts("1");
            else if(a < st)
                printf("%d\n", table[a]);
            else
                printf("%d\n", table[(a - st) % len + st]);
        }
    }
    else if(type[0] == '2' && type[1] == 'p')
    {
        scanf("%d", &n);
        for(; n--; )
        {
            long long l, r;
            scanf("%lld %lld", &l, &r);
            for(long long i = l; i <= r; i++)
                putchar(Miller_Rabin(i) ? 'p' : '.');
            puts("");
        }
    }
    else if(type[0] == '2' && type[1] == 'u')
    {
        scanf("%d", &n);
        seive();
        for(; n--; )
        {
            long long l, r;
            scanf("%lld %lld", &l, &r);
            for(int i = 0; i <= r - l; i++)
                mu[i] = id[i] = 1;
            for(int i = 1; i <= tot; i++)
            {
                long long p = prime[i], p2 = p * p;
                for(long long j = (l - 1) / p + 1; j * p <= r; j++)
                    mu[p * j - l] *= -1, id[p * j - l] *= p;
                for(long long j = (l - 1) / p2 + 1; j * p2 <= r; j++)
                    mu[p2 * j - l] = 0;
            }
            for(int i = 0; i <= r - l; i++)
            {
                if(!mu[i])
                    putchar('0');
                else
                {
                    id[i] = (i + l) / id[i];
                    if(id[i] == 1)
                        putchar(mu[i] > 0 ? '+' : '-');
                    else
                    {
                        long long x = sqrt(id[i]), y = id[i];
                        if(x * x == y)
                            mu[i] = 0;
                        else if(Miller_Rabin(y, 1))
                            mu[i] *= -1;
                        if(mu[i] > 0)
                            putchar('+');
                        else if(mu[i] < 0)
                            putchar('-');
                        else
                            putchar('0');
                    }
                }
            }
            puts("");
        }
    }
    else if(type[0] == '2' && type[1] == 'g' && type[2] == '?')
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            int l, r, p, x;
            if(i <= 2)
                scanf("%d %d %d", &l, &r, &p);
            else
                scanf("%d %d ?", &l, &r), p = 1515343657;
            x = p - 1;
            fac[0] = 0;
            for(int i = 2; i * i <= x; i++)
            {
                if(x % i == 0)
                {
                    fac[++fac[0]] = i;
                    if(i * i != x)
                        fac[++fac[0]] = x / i;
                }
            }
            for(int i = l; i <= r; i++)
                putchar(_check(i, p) ? 'g' : '.');
            puts("");
        }
    }
    else if(type[0] == '2' && type[1] == 'g')
    {
        scanf("%d", &n);
        fac[0] = 0;
        int x = 998244352;
        for(int i = 2; i * i <= x; i++)
        {
            if(x % i == 0)
            {
                fac[++fac[0]] = i;
                if(i * i != x)
                    fac[++fac[0]] = x / i;
            }
        }
        for(; n--; )
        {
            memset(vis, 0, sizeof vis);
            int l, r, p, x, g;
            scanf("%d %d %d", &l, &r, &p), x = p - 1;
            if(p == 998244353)
            {
                for(int i = l; i <= r; i++)
                    putchar(__check(i) ? 'g' : '.');
                puts("");
                continue;
            }
            g = 6, tot = 0;
            for(int i = 2; i * i <= x; i++)
            {
                if(x % i == 0)
                {
                    prime[++tot] = i;
                    for(; !(x % i); x /= i);
                }
            }
            if(x > 1) prime[++tot] = x;
            vis[0] = 1;
            for(int i = 1; i <= tot; i++)
            {
                for(int j = 1; j <= (p - 1) / prime[i]; j++)
                {
                    vis[j * prime[i]] = 1;
                }
            }
            _log[1] = 0;
            for(int i = 1, w = g; i <= p - 1; i++, w = 1ll * w * 1ll * g % p)
                _log[w] = i;
            for(int i = l; i <= r; i++)
            {
                if(i % p == 0) putchar('.');
                else putchar(vis[_log[i]] ? '.' : 'g');
            }
            puts("");
        }
    }
    return 0;
}