题目分析

他改变了传统题

本题极大地考察了和出题人心意相通的能力,它或许不能在茫茫人海中选出水平最高的选手,但一定能选出最适合当出题人 npy 的选手。

首先,出题人表示 “两个编号越相似,说明对应的两个功能的算法越接近。”。

那么 HOW TO 定义 “编号相似”?

我还觉得 1?2p 字符串长度都是 2 所以比较相似呢!

无语了。

测试点 1,2,3

观察测试点 1 前几项,发现是 $19^n$。对什么数取模呢?

是的你没猜错,就是 998244353!

至于输入的数字巨大,就要用欧拉定理降幂了。

测试点 4

没有给出模数,那就从输出里能找到的最大数字开始,暴力枚举模数咯,得到模数是 1145141(woc,恶臭模数)。

测试点 5

这个测试点就无法暴力枚举模数了,然后观察数据,发现数据里有这么两组:

第 7143 行,输入 264708066,输出 1996649514996338529

第 9368 行,输入 264708068,输出 1589589654696467295

得到 1996649514996338529*19*19 mod P =1589589654696467295

然后将 1996649514996338529*19*19-1589589654696467295 用 “待会儿反正用得着现在先写一个的 Pollard rho” 分解质因数(或者手动枚举较小质因数,用 python 计算,较小质因数里最大的是 23),得到最大的质因子 5211600617818708273,代入发现它的确是模数。

测试点 6,7

毫无意义的一个点,既然是 WA,那就是快速幂写错了,咋写错的?来,又到了考察你和出题人心意相通的时间了。写快速幂的时候乘法没有强制转 long long?写快速幂的时候有个地方忘记取模?正确答案是——

暴力一个个乘的时候取模没强制转 long long!

惊不惊喜?意不意外?刺不刺激?

接下来你写一个这样的代码,找到循环节:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=998244353;
map<int,int> mp;
int main()
{
    int x=1;mp[1]=0;
    for(RI i=1;;++i) {
        x=x*19%mod;
        if(mp.count(x)) {cout<<mp[x]<<" "<<i<<endl;break;}
        else mp[x]=i;
    }
    return 0;
}

就可以了。

测试点 8,9,10

2p?这是什么意思?

打开输入文件,每行两个数,第一个数要么是 2 要么是 5,第二个数则相对较大,而且是前一个数的倍数……

2 和 5,都是质数……

打开输出文件,若第一个数是 5,则输出 5 个数,否则输出第二个数字-1 个数……

每行只有 p.,这是什么……难道是像南蛮图腾那道题一样,要画图形吗?

2g 类的点,输出只有 g.,也就是说,编码给你什么字母,你输出就要画什么字母吗?

那为什么 2u 类的点输出是+-,或者. 呢?

这个. 有什么特殊的含义吗?

你分析了这么一大堆,一个小时已经过去了,你无奈地打开了题解,发现你前面分析的那一大堆屁用没有,这个点是输出判断 l 到 r 的每个数是不是质数(p=prime)

你会唾骂出题人,然后怀着愤恨的心情写 Miller Rabin。

测试点 11,12,13

上一组测试点,p=prime。你若大致理解了一点出题人的脑回路后,你就能猜到——

$u=\mu$

这个点还算有点技巧性,首先筛出 $10^6$内的所有质数,用 $\ln$级的时间求出它们对区间内数的贡献,并且将它们的倍数都除以它们。接下来再扫一遍区间里的所有数,它们的剩余值,要么是个质数(用 Miller Rabin 判断),要么是两个大于 $10^6$的质数的乘积(相同或者不同的,用 sqrt 开根检验即可)

测试点 14

g=原根。

暴力检验即可。

测试点 15

求一个数的所有原根。

先找出它的其中一个原根(譬如说,6

然后找出所有数关于该原根的指标(即 $6^d \equiv x \pmod{P}$,则称 $d$是 $x$的指标)

指标与 $\phi(P)$互质的,都是 $P$的原根。

用 $\phi(P)$的质因子将这些数都筛出来即可。

测试点 16

给了模数的范围,将所有范围内质数筛出,暴力检验前 15 个数字符不符合,得到模数等于 1515343657

完整代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef unsigned long long uLL;
typedef long long LL;
char typ[50];
//-------------------------------------
namespace work1{
    uLL mul(uLL x,uLL y,uLL mod) {
        if(x<1e9&&y<1e9) return x*y%mod;
        uLL re=0;
        for(;y;y>>=1,x=(x+x)%mod) if(y&1) re=(re+x)%mod;
        return re;
    }
    void work(uLL mod) {
        char S[50];int len,T;
        scanf("%d",&T);
        while(T--) {
            scanf("%s",S+1),len=strlen(S+1);
            uLL y=0,re=1,x=19;
            for(RI i=1;i<=len;++i) y=(mul(10uLL,y,mod-1)+(uLL)(S[i]-'0'))%(mod-1);
            for(;y;y>>=1,x=mul(x,x,mod)) if(y&1) re=mul(re,x,mod);
            printf("%llu\n",re);
        }
    }
};
namespace work2{
    const int mod=998244353;
    int a[100950],T;
    void work() {
        a[0]=1;for(RI i=1;i<=100944;++i) a[i]=a[i-1]*19%mod;
        scanf("%d",&T);
        while(T--) {
            uLL x;scanf("%llu",&x);
            if(x<=100944LL) printf("%d\n",a[x]);
            else printf("%d\n",a[(x-55245)%45699+55245]);
        }
    }
};
//-------------------------------------
LL qmul(LL x,LL y,LL p) {
    if(x<=2e9&&y<=2e9) return 1LL*x*y%p;
    return (x*y-(LL)((long double)x/p*y+0.5)*p+p)%p;
}
LL qpow(LL x,LL y,LL p) {
    LL re=1;
    for(;y;y>>=1,x=qmul(x,x,p)) if(y&1) re=qmul(re,x,p);
    return re;
}
int Miller_Rabin(LL n,int lim_kas) {
    if(n==2||n==3||n==5||n==7||n==11||n==13) return 1;
    if(n%2==0||n%3==0||n%5==0||n%7==0||n%9==0||n%11==0||n%13==0) return 0;
    LL k=n-1,t=0;
    while(!(k&1)) ++t,k>>=1;
    for(RI kas=1;kas<=lim_kas;++kas) {
        LL x=qpow(rand()%(n-2)+2,k,n),y;
        for(LL i=1;i<=t;++i) {
            y=x,x=qmul(x,x,n);
            if(x==1&&y!=1&&y!=n-1) return 0;
        }
        if(x!=1) return 0;
    }
    return 1;
}
namespace work3{
    void work() {
        LL l,r;int T;
        scanf("%d",&T);
        scanf("%lld%lld",&l,&r),puts("pp.p.p...");
        scanf("%lld%lld",&l,&r),puts("p.p...");
        scanf("%lld%lld",&l,&r),puts("pp.p.p...p.p..");
        scanf("%lld%lld",&l,&r);
        for(LL i=l;i<=r;++i) putchar(Miller_Rabin(i,10)?'p':'.');
        puts("");
    }
};
namespace work4{
    int tot,pri[1000005],is[1000005],mu[1000005];LL x[1000005];
    void work() {
        LL l,r;int T;
        scanf("%d",&T);
        scanf("%lld%lld",&l,&r),puts("--0-+-00+");
        scanf("%lld%lld",&l,&r),puts("-+-00+");
        scanf("%lld%lld",&l,&r),puts("--0-+-00+-0-++");
        scanf("%lld%lld",&l,&r);
        for(RI i=2;i<=1000000;++i) {
            if(!is[i]) pri[++tot]=i;
            for(RI j=1;j<=tot&&pri[j]*i<=1000000;++j) {
                is[pri[j]*i]=1;
                if(i%pri[j]==0) break;
            }
        }
        for(LL i=1;i<=r-l+1;++i) mu[i]=1,x[i]=l+i-1;
        for(RI i=1;i<=tot;++i) {
            LL tmp=1LL*pri[i]*((l-1)/pri[i]+1);
            for(LL j=tmp;j<=r;j+=pri[i]) {
                if(!mu[j-l+1]) continue;
                mu[j-l+1]=-mu[j-l+1],x[j-l+1]/=pri[i];
                if(x[j-l+1]%pri[i]==0) mu[j-l+1]=0;
            }
        }
        for(LL i=l;i<=r;++i) {
            if(x[i-l+1]!=1) {
                if(Miller_Rabin(x[i-l+1],2)) mu[i-l+1]=-mu[i-l+1];
                else {
                    LL tmp=sqrt((double)x[i-l+1]);
                    if(tmp*tmp==x[i-l+1]) mu[i-l+1]=0;
                }
            }
            putchar(mu[i-l+1]==0?'0':(mu[i-l+1]==-1?'-':'+'));
        }
        puts("");
    }
};
namespace work5{
    int pri[10],tot;bool is[13123120],isg[13123120];
    void QAQ1(int l,int r,int P) {
        if(P==998244353) tot=3,pri[1]=2,pri[2]=7,pri[3]=17;
        else tot=4,pri[1]=2,pri[2]=3,pri[3]=4003,pri[4]=15773;
        for(RI i=l;i<=r;++i) {
            int flag=1;
            if(qpow(i,P-1,P)!=1) flag=0;
            else {
                for(RI j=1;j<=tot;++j)
                    if(qpow(i,(P-1)/pri[j],P)==1) {flag=0;break;}
            }
            putchar(flag?'g':'.');
        }
        puts("");
    }
    void QAQ2() {
        const int g=6;
        tot=8,pri[1]=2,pri[2]=3,pri[3]=5;
        pri[4]=7,pri[5]=11,pri[6]=13,pri[7]=19,pri[8]=23;
        for(RI i=1;i<=tot;++i)
            for(RI j=pri[i];j<=13123110;j+=pri[i]) is[j]=1;
        for(RI i=1,g=6;i<=13123110;++i,g=6LL*g%13123111) if(!is[i]) isg[g]=1;
        for(RI i=1;i<=13123110;++i) putchar(isg[i]?'g':'.');
    }
    void work() {
        int l,r,P,T;
        scanf("%d",&T);
        scanf("%d%d%d",&l,&r,&P),puts(".g");
        scanf("%d%d%d",&l,&r,&P),puts(".g.gg...g");
        if(T==4) {
            scanf("%d%d%d",&l,&r,&P),QAQ1(l,r,P);
            scanf("%d%d%d",&l,&r,&P),QAQ1(l,r,P);
        }
        else {
            scanf("%d%d",&l,&r);
            if(l==1) QAQ2();
            else QAQ1(l,r,1515343657);
        }
    }
};
//-------------------------------------
int main()
{
    srand(19260817);
    scanf("%s",typ);
    if(!strcmp(typ,"1_998244353")) work1::work(998244353LL);
    else if(!strcmp(typ,"1?")) work1::work(1145141LL);
    else if(!strcmp(typ,"1?+")) work1::work(5211600617818708273LL);
    else if(!strcmp(typ,"1wa_998244353")) work2::work();
    else if(!strcmp(typ,"2p")) work3::work();
    else if(!strcmp(typ,"2u")) work4::work();
    else work5::work();
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

1 条评论

Remmina · 2019年6月2日 11:37 下午

肽可啪了 QAQ
真庆幸自己学了 3 年信息学后还有呼吸和脉搏

发表评论

电子邮件地址不会被公开。 必填项已用*标注