题目分析
他改变了传统题
本题极大地考察了和出题人心意相通的能力，它或许不能在茫茫人海中选出水平最高的选手，但一定能选出最适合当出题人 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;
}
1 条评论
Remmina · 2019年6月2日 11:37 下午
肽可啪了 QAQ
真庆幸自己学了 3 年信息学后还有呼吸和脉搏