Luogu5285 骗分过样例

Arahc 11.0
  2022-01-25 08:00 2022-01-25 08:00 创建   2023-03-17 08:34:46 2023-03-17 08:34:46 更新      2.4k 字  11 分钟  

题面

简化题意

给出本题的 1616 个数据和一些提示。每组数据对应的算法不一定相同。你需要写一个代码通过本题（数据很大，不能打表输出）。

题解

case1,2,3

提示为 1_998244353，不难猜测模数是 998244353998244353。

打开前三个点，观察前几个数字，发现输入文件 是 0,1,2,3⋯0,1,2,3\cdots，输出文件是 1,19,361,6859⋯1,19,361,6859\cdots。不难猜出这三个点在计算 19x mod 99824435319^x\bmod 998244353。

  • 第一个点直接暴力乘。
  • 第二个点快速幂即可。
  • 第三个点数值很大，要一边输入一边用欧拉定理把指数模下来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
__int128 mod;
inline int reads(){
    int x=0;char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9') x=((x<<1)+(x<<3)+(c^48))%(mod-1),c=getchar();
    return x;
}
inline __int128 mi(__int128 a,__int128 p){
    __int128 res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}
inline void sol(int P){
    mod=P;
    for(register int T=read();T>0;--T)
        write(mi(19,reads())),putchar('\n');
}

case4

提示变成了 1?，观察输入和输出的前几个数发现还是计算 19x19^x。继续观察发现模数不一样了。

在输出里面随便找一个很大的答案，比如 11382611138261。因为数值普遍很小，推测模数不是很大。从这个数开始往上枚举质数，检验是否成立即可。最后发现质数为 11451411145141。

1
2
3
4
5
6
7
8
9
10
freopen("prime.txt","w",stdout);
   memset(isp,1,sizeof(isp)),isp[1]=0;
   for(register int i=2;i<=n;++i) if(isp[i]){
       pr[++cnt]=i;
       for(register int j=i;j<=n;j+=i)
           isp[j]=0;
   }
   for(register int i=1;i<=cnt;++i) if(pr[i]>1138261){
       write(pr[i]),putchar(' '),puts("627811703016764290815178977207148434322");
   }
1
2
3
4
5
6
7
8
freopen("prime.txt","r",stdin);
  while(mod=read()){
      if(mod==0) break;
      n=reads();
      if(mi(19,n)==642666){
          printf("find : %lld\n",mod);
      }
  }

case5

提示为 1?+，模数还是不确定。打开发现模数非常大，但是还是在计算 19x19^x。这里的数值都顶到 long long 边上了，显然不能暴力找。

考虑到如果三个数 a=19x mod p,b=19y mod p,c=19x−y mod pa=19^x\bmod p,b=19^y\bmod p,c=19^{x-y}\bmod p，则：

a−bc≡19x−19y19x−y≡0(modp)a-bc \equiv 19^x - 19^y19^{x-y} \equiv 0 \pmod p

于是有 p∣a−bcp\mid a-bc。找出合法的三元组 (a,b,c)(a,b,c)，求 a−bca-bc 的 gcd⁡\gcd 即可。pp 为这个数的约数。如果能找到公约数，枚举约数算是简单的。具体实现可以考虑将指数排序，开个 map 检查指数是否存在。T2T^2 枚举 x,yx,y 查询是否存在 x−yx-y。复杂度 T2log⁡TT^2\log T，3s 可以跑出来。

非常幸运，不需要枚举约数，公约数就是答案。最终发现模数为 52116006178187082735211600617818708273。找模数的代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map<int,int> mp;
FILE *in=fopen("data5.in","r"),*out=fopen("data5.ans","r");
for(register int i=1;i<=10000;++i){
    fscanf(in,"%lld",&q[i].p),
    fscanf(out,"%lld",&q[i].a);
    mp[q[i].p]=q[i].a;
}
sort(q+1,q+1+10000,cmp);
for(register int i=2;i<=10000;++i)
    for(register int j=i+1;j<=10000;++j)
        if(mp.count(q[j].p-q[i].p)){
            int a=q[j].a,b=q[i].a,c=mp[q[j].p-q[i].p];
            if(g==-1) g=a-b*c;
            else g=gcd(g,a-b*c);
        }
write(g<0?-g:g),putchar('\n');

case6,7

提示是 1wa_998244353。输出文件里有负数。这个比较难发现是什么，最后会发现是暴力算快速幂的时候爆了 int。

显然爆 int 的快速幂和爆 int 的普通暴力算结果是不一样的。考虑爆 int 的数值模 998244353998244353 的周期，暴力算一下这个周期是什么：

1
2
3
4
5
6
7
8
9
10
11
12
int p=1;
mp[1]=0;
for(register int i=1;i<=10000000;++i){
    p=p*19%mod;
    if(mp.count(p)){
        write(i),putchar('\n');
        write(mp[p]),putchar('\n');
        return 0;
    }
    mp[p]=i;
    
}

从第 5524555245 项开始，到第 100944100944 项。这段数是循环节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline void WA(){
    mod=998244353;
    mp[1]=0,a[0]=1;
    int32_t p=1,tim,st;
    for(register int i=1;;++i){
        p=p*19,p%=mod;
        if(mp.count(p)){
            tim=i,st=mp[p];
            break;
        }
        mp[p]=i,a[i]=p;
    }
    for(register int T=read();T>0;--T){
        int n=read();
        if(n<st) write(a[n]);
        else write(a[(n-st)%(tim-st)+st]);
        putchar('\n');
    }
}

case8,9,10

提示为 2p。输入数据给定了两个数，输出包含点和字母 p 的字符串。进一步研究字符串长度与输入的数字 a,ba,b 满足 len=b−a+1len=b-a+1，再进一步就会发现，题目要求区间每个数是否是质数（prime）。直接跑 Miller Rabin 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
namespace Miller{
    inline int mi(__int128 a,int p,int mod){
        __int128 res=1;
        while(p){
            if(p&1) res*=a,res%=mod;
            a*=a,a%=mod,p>>=1;
        }
        return res;
    }
    inline bool chk(int x,int p){
        if(mi(p%x,x-1,x)!=1) return 0;
        for(register int i=x-1;!(i&1);){
            i>>=1;
            int t=mi(p%x,i,x);
            if(t!=1 && t!=(x-1)) return 0;
            if(t==x-1) return 1;
        }
        return 1;
    }
    inline bool check(int x){
        if(x<=N) return isp[x];
        if(!(x&1) || !chk(x,24251)) return 0;
        return 1;
    }
}

namespace Prime{
    inline void print(bool x){
        putchar(x?'p':'.');
    }
    inline void init(int n){
        memset(isp,1,sizeof(isp)),isp[1]=0,mu[1]=1;
        for(register int i=2;i<=n;++i){
            if(isp[i]){
                mu[i]=-1,
                pr[++cnt]=i;
            }
            for(register int j=1;j<=cnt && i*pr[j]<=n;++j){
                isp[i*pr[j]]=0;
                if(i%pr[j]==0){
                    mu[i*pr[j]]=0;
                    break;
                }
                mu[i*pr[j]]=-mu[i];
            }
        }
    }
    inline void sol(){
        for(register int T=read();T>0;--T){
            int l=read(),r=read();
            for(register int i=l;i<=r;++i)
                print(Miller::check(i));
            putchar('\n');
        }
    }
}

case11,12,13

提示变成了 2u。猜测不再是查询一个数是否为质数。打开输出发现一堆正负号和零。不难猜测这个是查询区间每个数的 μ\mu。

  • 第一个点线性筛。
  • 第二个点 min25 筛。
  • 第三个点，用 [1,106][1,10^6] 的质数筛一遍区间内的数字。剩余不是 1 的数字一定要么是两个质因数乘起来，要么是质数。分别判断即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
namespace Mu{
    int prep[1000006],u[1000006];
    inline void print(int x){
        if(!x) putchar('0');
        else if(x<0) putchar('-');
        else putchar('+');
    }
    inline void init(int L,int R){
        for(register int i=L;i<=R;++i)
            prep[i-L]=i,u[i-L]=-1;
        for(register int i=1;i<=cnt;++i){
            int st=L/pr[i]*pr[i];
            for(register int j=st<L?st+pr[i]:st;j<=R;j+=pr[i]) if(u[j-L]){
                u[j-L]=-u[j-L],
                prep[j-L]/=pr[i];
                if(prep[j-L]%pr[i]==0)
                    u[j-L]=0;
            }
        }
        for(register int i=L;i<=R;++i) if(u[i-L]){
            if(prep[i-L]==1){
                u[i-L]=-u[i-L];
                continue;
            }
            int x=(int)sqrt(prep[i-L]);
            if(x*x==prep[i-L]){
                u[i-L]=0;
                continue;
            }
            if(!Miller::check(prep[i-L]))
                u[i-L]=-u[i-L];
        }
    }
    inline void sol(){
        for(register int T=read();T>0;--T){
            int l=read(),r=read();
            if(T==1) init(l,r);
            for(register int i=l;i<=r;++i){
                if(i<=N) print(mu[i]);
                else print(u[i-l]);
            }
            putchar('\n');
        }
    }
}

case14,15

提示为 2g。打开输入发现除了区间 l,rl,r 外还输入了质数 998244353998244353。推测是求出 998244353998244353 的所有原根。

这个质数的原根很好判断，因为其 φ\varphi 值的质因数只有三种，原根判定定理暴力做就可以了。

对于第 1515 个点，质数为 1312311113123111，它的 φ\varphi 八种质因子，区间也很大。

用这个数的质因数去标记所有和原数不互质的数字。就可以快速判断互质关系了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
inline int mi(int a,int p,int mod){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}
inline void fact(int n,int k){
    tot=0,
    memset(prp,1,sizeof(prp));
    for(register int i=1;i<=cnt && pr[i]*pr[i]<=n;++i) if(n%pr[i]==0){
        fat[++tot]=pr[i];
        while(n%pr[i]==0)
            n/=pr[i];
        for(register int j=pr[i];j<=k;j+=pr[i])
            prp[j]=0;
    }
    if(n>1){
        fat[++tot]=n;
        for(register int j=n;j<=k;j+=n)
            prp[j]=0;
    }
}
inline int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
inline bool isg(int x,int p){
    for(register int i=1;i<=tot;++i)
        if(mi(x,(p-1)/fat[i],p)==1)
            return 0;
    return 1;
}
inline void sol(){
    fact(998244352,0);
    for(register int T=read();T>0;--T){
        int l=read(),r=read(),n=read();
        if(n==998244353){
            for(register int i=l;i<=r;++i)
                print(isg(i,998244353));
            putchar('\n');
            continue;
        }
        fact(n-1,n-1);
        for(register int i=1,f=1,g=6;i<=n-1;++i){
            f=f*g%n;
            if(f>=l && f<=r && prp[i]) tag[f-l]=1;
        }
        for(register int i=l;i<=r;++i)
            print(tag[i-l]);
        putchar('\n');
    }
}

case16

提示为 2g?，结合前面做的 1g?，猜测是模数不知道，一打开果然如此。但是输入文件里还提示了这个模数的范围为 [109,2×109][10^9,2\times 10^9] 内的质数。

注意到不同质数在同一区间内原根的分布是比较混乱的。暴力枚举这里的质数，只需要把前几个 gg 代入检验就可以了，几分钟就跑出来了，模数为 15153436571515343657。这个数的 φ\varphi 只有四个质因子，可以和 998244353998244353 那个用同一个做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void Mod(int P){
    fact(998244352,0);
    for(register int T=read();T>0;--T){
        int l=read(),r=read(),n=read();
        if(n==998244353){
            for(register int i=l;i<=r;++i)
                print(isg(i,998244353));
            putchar('\n');
            continue;
        }
        fact(P-1,0);
        for(register int i=l;i<=r;++i)
            print(isg(i,P));
        putchar('\n');
    }
}

代码？

其实就是把上面的代码拼起来而已。这里就不放出来了。太长了占版面。

  • 标题: Luogu5285 骗分过样例
  • 作者: Arahc
  • 创建于 : 2022-01-25 08:00:00
  • 更新于 : 2023-03-17 08:34:46
  • 链接: https://arahc.github.io/2022/01/25/【题解】Luogu5285-骗分过样例/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
Luogu5285 骗分过样例
  1. 题面
  2. 题解
    1. case1,2,3
    2. case4
    3. case5
    4. case6,7
    5. case8,9,10
    6. case11,12,13
    7. case14,15
    8. case16
  3. 代码？