1 条题解

  • 0
    @ 2025-8-24 22:09:03

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar TheLostWeak
    **

    搬运于2025-08-24 22:09:03，当前版本为作者最后更新于2019-04-15 09:32:02，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    在博客查看

    大致题意： 把所有输入输出数据都给你，并给你一定提示，让你写出正确的程序。

    Case 1~Case 3

    首先让我们点开数据，发现输入为 0,1,2,3....0,1,2,3.... ，输出为 1,19,361,6859...1,19,361,6859...。

    不用多说，显然是求 19x19^x。

    再看功能编号 1_998244353 ，显然 998244353998244353 是模数。

    于是，用快速幂就可以过前两个点。

    然后就会发现第三个点的 xx 很大。。。

    因此就要借助欧拉定理来进行求解。

    由欧拉定理可知：aϕ(MOD)≡1(mod MOD)a^{\phi(MOD)}\equiv1(mod\ MOD)。

    所以，ax≡ax%ϕ(MOD)(mod MOD)a^x\equiv a^{x\%\phi(MOD)}(mod\ MOD)。

    由于 MODMOD 是个质数，所以 ϕ(MOD)\phi(MOD) 就等于 MOD−1MOD-1。

    这样一来，我们只需要在读入 xx 时边读边向 MOD−1MOD-1 取模，即可。

    代码如下：

    I void Qmul(LL& x,CL y,CL X) {RL k=(LL)((1.0L*x*y)/(1.0L*X)),t=x*y-k*X;t-=X;W(t<0) t+=X;x=t;}//快速乘
I LL Qpow(RL x,RL y,CL X) {RL t=1;W(y) y&1&&(Qmul(t,x,X),0),Qmul(x,x,X),y>>=1;return t;}//快速幂
class CommonPow19Solver//求解19^x
{
	public:
		I void Solve(CL X)//求解答案，X为模数
		{
			RI n;RL x;for(F.read(n);n;--n)
				F.read_with_X(x,X-1),F.writeln(Qpow(19,x,X));//读入时向X-1取模，然后快速幂
		}
}Common;

    Case 4

    看数据显然还是求 19x19^x。

    但功能编号里本该放模数的位置变成了?是什么鬼？

    仔细观察，似乎答案都不是很大。

    因此我们可以考虑通过枚举的方式来确定模数。

    然后有几点需要注意：

    • 枚举下界是所有元素最大值（11450991145099）+1+1。
    • 验证时不要像我一开始那样naive地对于每个数去验证，其实只要验证一下第一个大数 627811703016764290815178977207148434322627811703016764290815178977207148434322 的答案是否正确即可。
    • 模数需要为质数，因为我们要相信出题人很良心， 不然 ϕ\phi 不好求。而判断其是否为质数可以使用MillerRabin\texttt{MillerRabin}。（我们会发现接下来经常要用到MillerRabin\texttt{MillerRabin}）

    于是就可以得到找模数代码如下：

    #include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define RL Reg LL
#define Con const
#define CI Con int&
#define CL Con LL&
#define I inline
#define W while
#define LL long long
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
#define Shl(x) ((x<<=1)>=X&&(x-=X))
using namespace std;
LL X;
class MillerRabin//MillerRabin判素数板子
{
	private:
		#define Pcnt 12
		Con int P[Pcnt]={2,3,5,7,11,13,17,19,61,2333,4567,24251};
		I LL Qmul(CL x,CL y,CL X) 
		{
			RL k=(LL)((1.0L*x*y)/(1.0L*X)),t=x*y-k*X;
			t-=X;W(t<0) t+=X;return t;
		}
		I LL Qpow(RL x,RL y,CL X) 
		{
			RL t=1;W(y) y&1&&(t=Qmul(t,x,X)),x=Qmul(x,x,X),y>>=1;
			return t;
		}
		I bool Check(CL x,CI p)
		{
			if(Qpow(p%x,x-1,x)^1) return false;
			RL k=x-1,t;W(!(k&1))
			{
				if((t=Qpow(p%x,k>>=1,x))^1&&t^(x-1)) return false;
				if(!(t^(x-1))) return true;
			}return true;
		}
	public:
		I bool IsPrime(CL x)
		{
			if(x<2) return false;
			for(RI i=0;i^Pcnt;++i) {if(!(x^P[i])) return true;if(!Check(x,P[i])) return false;}
			return true;
		}
}MR;
I void Qmul(LL& t,RL y) {RL x=t;t=0;W(y) y&1&&Inc(t,x),Shl(x),y>>=1;}//快速乘
I LL Qpow(RL y) {RL x=19,t=1;W(y) y&1&&(Qmul(t,x),0),Qmul(x,x),y>>=1;return t;}//快速幂
I void Sread(Con string& s,LL& x,CL X)//从字符串中边取模边读入
{
	for(RI i=x=0,l=s.length();i^l;++i) 
		x=(((x<<3)+(x<<1))%X+(s[i]&15))%X;
}
I void FindX(CL l,CL r)//寻找模数
{
	RI n;RL i,x;Reg string st="627811703016764290815178977207148434322";//存下第一个大数
	for(i=l;i<=r;++i) if(MR.IsPrime(X=i))//枚举数，判断其是否为质数
		if(Sread(st,x,i-1),!(Qpow(x)^642666)) return (void)(printf("%lld",X));//读入，判断第一个数答案是否正确
}
int main() {return FindX(1145100,1500000),0;}//确定枚举范围

    运行结果：

    1145141

    然后就可以套用之前的板子，只需要在调用时改成：

    Common.Solve(1145141);

    Case 5

    1?+ 。。。一看就是 1? 的升级版。

    我们可以发现模数似乎特别大。

    暴枚肯定不行了，我们需要换一种思路。

    考虑怎样才能确定模数的大致范围？

    于是就能想到这样一种情况：找到最相近的两个数 x,yx,y（x<yx<y），使得 xx 的答案大于 yy 的答案。

    则我们通过 xx 的答案求出yy的答案在不取摸情况下为 ansx∗19y−xans_x*19^{y-x}，则模数必然为 ansx∗19y−x−ansyans_x*19^{y-x}-ans_y 的因数。

    具体实现就是将每个数与其对应的答案一起按数的大小排个序，然后扫一遍即可。

    代码如下：

    #include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define RL Reg LL
#define Con const
#define CI Con int&
#define CL Con LL&
#define I inline
#define W while
#define N 10000
#define LL long long
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define eps 1e-10
#define ull unsigned long long
using namespace std;
int n;char st[5];struct data {LL x,v;I bool operator < (Con data& t) Con {return x<t.x;}}s[N+5];
I int Pow(CI x,CI y) {RI i,t=1;for(i=1;i<=y;++i) t*=x;return t;}
int main()
{
	RI res=0;RL i,Mx=0;FILE *F1=fopen("software5.in","r"),*F2=fopen("software5.ans","r");
	for(fscanf(F1,"%s%d",st,&n),i=1;i<=n;++i) 
		fscanf(F1,"%lld",&s[i].x),fscanf(F2,"%lld",&s[i].v),Gmax(Mx,s[i].v);//读入每个数及其对应的答案，Mx统计答案最大值
	for(sort(s+1,s+n+1),i=1;i^n;++i) s[i].v>s[i+1].v&&//排序，然后找到符合条件的一对数
		(!res||s[i+1].x-s[i].x<s[res+1].x-s[res].x)&&(res=i);
	printf("Max=%lld\n%lld %lld\n%lld %lld\n",Mx,s[res].x,s[res].v,s[res+1].x,s[res+1].v);//输出
	return 0;
}

    运行结果：

    Max=5211500658258874318
264708066 1996649514996338529
264708068 1589589654696467295

    则可以计算出 ansyans_y 不取模为 1996649514996338529∗361=7207904749136782089691996649514996338529*361=720790474913678208969，然后减去取模后的 ansyans_y，得到模数为 719200885258981741674719200885258981741674 的因数。

    但对于这么大一个爆 long long 的数，我们该如何找它的因数呢？

    没关系，我们有Python，然后就可以枚举寻找一个较小的因数，来确定较大的那个因数。

    但考虑到在根号范围内寻找依然太慢，于是要加两个优化：

    • 我们要相信出题人足够良心，模数不会爆 long long，因此对于一开始模数爆 long long 的情况可以直接跳过。
    • 我们之前不是得到了一个答案下界（即最大值 +1+1）吗？当另一个较大的因数小于等于最大值时，我们就可以直接结束循环了。

    于是效率大大提高，很快就能得出答案。

    代码如下：

    v=719200885258981741674#已知答案是这个数的因数
Mx=5211500658258874319#答案下界
lim=2**63#long long范围
i=0#初始化i为0
while(1):
    i+=1#将i加1
    if(v//i>=lim):continue#如果此时答案超过long long范围，跳过
    if(v%i==0):print (v//i)#如果找到答案，输出
    if(v//i<Mx):break#如果小于答案下界，结束循环

    运行结果：

    5211600617818708273

    然后照样套用之前的板子，只需改成：

    Common.Solve(5211600617818708273);

    Case 6~Case 7

    这个就很有趣了，1wa_998244353，显然还是在模 998244353998244353 意义下求 19x19^x，但这个 wa 是什么鬼？

    点开输出，可以发现有负数！

    便能想到或许是在暴力乘的时候写成了：

    x=19*x%X;

    然而19*x爆int了，于是就有了负数。

    但这样显然不能快速幂。

    不过，这样或许会出现循环节！

    于是就可以想到借助 map，写出这样一份代码：

    #include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define RL Reg LL
#define Con const
#define CI Con int&
#define CL Con LL&
#define I inline
#define W while
#define N 10000
#define LL long long
#define X 998244353
using namespace std;
map<int,int> p;
int main()
{
	for(RI i=1,x=1;;++i)
		if(p[x=19*x%X]) return printf("%d %d",p[x],i-p[x]),0;//找到循环节则输出开始循环的位置和周期
		else p[x]=i;return 0;//否则，继续处理
}

    运行结果：

    55245 45699

    然后就可以写出求解这个问题的代码了：

    class OverFlowPow19Solver//求解溢出情况下19^x
{
	private:
		#define A 55244//开始循环的位置
		#define B 45699//循环周期
		#define X 998244353//模数
		int a[A+B+5];
	public:
		I void Solve()
		{
			RI n,i;RL x;for(a[0]=i=1;i<=A+B;++i) a[i]=19*a[i-1]%X;//打表
			for(F.read(n);n;--n) F.read(x),F.writeln(a[x<=A?x:(x-A)%B+A]);//输出答案
		}
		#undef X
}OverFlow;

    Case 8~Case 10

    看到功能编号变成了 2，说明接下来就不是求 19x19^x 了。

    首先，研究数据可得，p 为 Prime（素数），然后题目要求就是对一段区间内质数输出 pp，合数输出 ..。

    判断大素数就可以用之前提到过的 MillerRabin\texttt{MillerRabin}，详见此博客：初学MillerRabin素数测试。

    然后声明一下，这道题中我只用22和33来测试理论上来讲是不够严谨的，但错误概率小，依然过了。

    而且主要是为了下一个部分分卡常需要。。。

    代码如下：

    class MillerRabin//MillerRabin判素数板子
{
	private:
		I bool Check(CL x,CI p)
		{
			if(Qpow(p%x,x-1,x)^1) return false;
			RL k=x-1,t;W(!(k&1))
			{
				if((t=Qpow(p%x,k>>=1,x))^1&&t^(x-1)) return false;
				if(!(t^(x-1))) return true;
			}return true;
		}
	public:
		I bool IsPrime(CL x) 
		{
			return !(x^2)||!(x^3)||(x&1&&x%3&&Check(x,2)&&Check(x,3));
		}
}MR;
class PrimeSolver//判断一段区间内每个数是否为质数
{
	public:
		I void Solve()
		{
			RI n;RL i,l,r;for(F.read(n);n;--n,F.writec('\n'))
				for(F.read(l,r),i=l;i<=r;++i) F.writec(MR.IsPrime(i)?'p':'.');//输出
		}
}Prime;

    Case 11~Case 13

    看到 u，以及输出为 0,+,−0,+,-，便不难想到是求莫比乌斯函数μ\mu。

    关于莫比乌斯函数的定义可以参考这篇博客：初学莫比乌斯反演。

    观察可得，区间的左边界和右边界虽然值域高达 101810^{18}，但是实际区间长度却很小。

    则我们可以考虑先用线性筛筛出 10610^6 以内所有质数及所有数的μ\mu值。

    然后，对于小于等于 10610^6 的询问，直接输出筛到的 μ\mu。

    否则，先把其所有小于等于 10610^6 的质因数全部除去，同时统计 μ\mu 值。

    然后，最后得到的这个数要么为 11，否则显然由最多两个大于 10610^6 的质数组成。

    于是，进行以下操作：

    • 用 MillerRabin\texttt{MillerRabin} 判断其是否为质数，若是，将其先前统计的 μ\mu 值乘上 −1-1 然后输出。
    • 否则，我们判断其是否为完全平方数，若是，则说明它是一个质数的平方，因此将其 μ\mu 值改为 00。
    • 否则，它由两个互不相同的质数组成，因此将其先前统计的 μ\mu 值乘上 (−1)∗(−1)(-1)*(-1)，就相当于乘 11，无需任何操作。

    然后注意卡常。

    具体代码如下：

    class LineSiever//线性筛
{
	private:
		#define SZ 1000000
	public:
		int Pc,mu[SZ+5],P[SZ+5];
		I void Sieve(CI S)
		{
			for(RI i=(mu[1]=1,2),j;i<=S;++i)
				for(!P[i]&&(mu[P[++Pc]=i]=-1),j=1;j<=Pc&&1LL*i*P[j]<=S;++j)
					if(P[i*P[j]]=1,i%P[j]) mu[i*P[j]]=-mu[i];else break;
		}
}L;
class MuSolver//求一段区间内每个数的μ值
{
	private:
		#define S 1000000
		#define C(x) ((x)?(~(x)?'+':'-'):'0')
		int g[S+5];ull v[S+5];
	public:
		I void Solve()
		{
			RI n,i,j,lim,len;RU x,y,l,r;for(L.Sieve(S),F.read(n);n;--n)
			{
				if(F.read(l,r),l<=S)//对于筛过的数，直接输出μ值
				{
					for(i=l,lim=min(r,S);i<=lim;++i) F.writec(C(L.mu[i]));
					if(F.writec('\n'),r<=S) continue;l=S+1;
				}
				for(len=r-l+1,i=len;i;--i) g[i]=v[i]=1;//初始化
				for(i=L.Pc;i;--i) for(j=(l+L.P[i]-1)/L.P[i]*L.P[i]-l+1;j<=len;j+=L.P[i])//枚举质数及其倍数
					(l+j-1)/L.P[i]%L.P[i]?g[j]&&(g[j]*=-1,v[j]*=L.P[i]):(g[j]=0);//统计μ值
				for(i=1;i<=len;++i) g[i]&&(i+l-1)^v[i]&&(MR.IsPrime(x=(i+l-1)/v[i])?//如果不为1
					g[i]*=-1:(y=sqrt(x),y*y==x)&&(g[i]=0)),F.writec(C(g[i]));//为质数则将μ值乘-1，为完全平方数则将μ值变为0，然后输出
				F.writec('\n');
			}
		}
		#undef S
}Mu;

    Case 14

    g 等于原根，这就相当于要我们求一段区间内每个数是否为给定质数的原根。

    考虑原根定义：一个数 xx 是质数 pp 的原根，当且仅当对于ϕ(p)\phi(p)（即 p−1p-1）的任意质因数 qq，xϕ(p)q%p≠1x^{\frac{\phi(p)}q}\%p≠1。

    发现这个点的模数全为 998244353998244353，对此直接暴力分解 998244352998244352，然后暴力判断即可：

    class GRSolver//判断一段区间内每个数是否为给定质数的原根
{
	private:
		#define S 100000
		int cnt,s[S+5];
		I void Init(CI x)//分解
		{
			RI i,t=x;for(cnt=0,i=1;1LL*L.P[i]*L.P[i]<=t;++i)
				if(!(t%L.P[i])) {s[++cnt]=L.P[i];W(!(t%L.P[i])) t/=L.P[i];}//存储质因数
			t^1&&(s[++cnt]=t);//存储质因数
		}
		I bool IsGR(CI x,CI X)//暴力判断
		{
			for(RI i=1;i<=cnt;++i) if(Qpow(x,(X-1)/s[i],X)==1) return false;
			return true;
		}
	public:
		I void Solve()
		{
			RI n,i,l,r,X;for(L.Sieve(S),F.read(n);n;--n)
				for(Init(X-1),i=l;i<=r;++i) F.writec(IsGR(i,X)?'g':'.');//暴力
		}
}GR;

    Case 15

    这个点在原有模数基础上多了个 1312311113123111。

    然后暴力就跑不过了。。。

    于是我们就要用一种特殊的方式来做。

    首先，我们暴力找出其最小的一个原根（实际上任意一个原根都可以）。

    接下来求出每个数以这个最小原根为原根的指标。

    然后判断每个数的指标与 ϕ(X)\phi(X)（即 X−1X-1）是否互质即可判断这个数是否为原根。

    但判互质这里需要一种类似于筛的东西。

    考虑和上个点一样先求出X−1X-1的全部质因数，然后把这些质因数的倍数全部打个标记。

    最后指标没被打标记的就是原根。

    与上一个点整合后的代码如下：

    class GRSolver//判断一段区间内每个数是否为给定质数的原根
{
	private:
		#define S 100000
		#define V 13123111
		int cnt,s[S+5],pos[V+5],vis[V+5];
		I void Init(CI x)//分解
		{
			RI i,t=x;for(cnt=0,i=1;1LL*L.P[i]*L.P[i]<=t;++i)
				if(!(t%L.P[i])) {s[++cnt]=L.P[i];W(!(t%L.P[i])) t/=L.P[i];}//存储质因数
			t^1&&(s[++cnt]=t);//存储质因数
		}
		I bool IsGR(CI x,CI X)//暴力判断
		{
			for(RI i=1;i<=cnt;++i) if(Qpow(x,(X-1)/s[i],X)==1) return false;
			return true;
		}
		I void Sieve(CI l,CI r,CI X)//筛
		{
			static int T=0;RI i,j,p,t;++T;//初始化
			for(t=1;!IsGR(t,X);++t);for(i=1,p=t;i^X;++i) pos[p]=i,p=1LL*p*t%X;//暴力找到一个最小的原根，然后求指标
			for(i=1;i<=cnt;++i) for(j=s[i];j<X;j+=s[i]) vis[j]=T;//打标记
			for(i=l;i<=r;++i) F.writec(vis[pos[i]]^T?'g':'.');//输出
		}
	public:
		I void Solve()
		{
			RI n,i,l,r,X;for(L.Sieve(S),F.read(n);n;--n)
			{
				if(X==998244353) for(Init(X-1),i=l;i<=r;++i) F.writec(IsGR(i,X)?'g':'.');//暴力
				else Init(X-1),Sieve(l,r,X);F.writec('\n');//筛
			}
		}
}GR;

    Case 16

    2g?，又是一个要确定模数的，不过这次良心地给了模数的范围，只不过范围大小是 10910^9。。。

    考虑出题人会怎么卡你？肯定是把模数放在靠中间的位置。

    因此，我们就从中间向两边枚举！

    然后对于枚举到的数如何判断呢？

    首先依然是 MillerRabin\texttt{MillerRabin} 判素数。

    接下来，我们只验证前 5050 个答案，如果这个数的 x−12\frac {x-1}2 次方为 11 但是这一位应该是原根，就说明 xx 不是要求的模数。

    代码如下：

    #include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define M 1500000000
#define S 50
using namespace std;
Con string s="...ggg..gg.g...g..gg..g.gg......gg..g......gg..gg.";
I int Qpow(RI x,RI y,CI X) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
class MillerRabin//MillerRabin判素数板子
{
	private:
		#define Pcnt 12
		Con int P[Pcnt]={2,3,5,7,11,13,17,19,61,2333,4567,24251};
		I bool Check(CI x,CI p)
		{
			if(Qpow(p%x,x-1,x)^1) return false;
			RI k=x-1,t;W(!(k&1))
			{
				if((t=Qpow(p%x,k>>=1,x))^1&&t^(x-1)) return false;
				if(!(t^(x-1))) return true;
			}return true;
		}
	public:
		I bool IsPrime(CI x)
		{
			if(x<2) return false;
			for(RI i=0;i^Pcnt;++i) {if(!(x^P[i])) return true;if(!Check(x,P[i])) return false;}
			return true;
		}
}MR;
I bool Check(CI X)//验证前50个答案
{
	for(RI i=0;i^S;++i) if(Qpow(i+233333333,X-1>>1,X)==1&&s[i]^'.') return false;//产生冲突就返回false
	return true;//返回true
}
int main()
{
	for(RI i=1;;i+=2)//从中间向外枚
	{
		if(MR.IsPrime(M+i)&&Check(M+i)) return printf("%d",M+i),0;//先判质数，再验证
		if(MR.IsPrime(M-i)&&Check(M-i)) return printf("%d",M-i),0;//同上
	}return 0;
}

    运行结果：

    1515343657

    再与先前代码一整合，就可以得到这一部分的最终代码：

    class GRSolver//判断一段区间内每个数是否为给定质数的原根
{
	private:
		#define S 100000
		#define V 13123111
		int cnt,s[S+5],pos[V+5],vis[V+5];
		I void Init(CI x)//分解
		{
			RI i,t=x;for(cnt=0,i=1;1LL*L.P[i]*L.P[i]<=t;++i)
				if(!(t%L.P[i])) {s[++cnt]=L.P[i];W(!(t%L.P[i])) t/=L.P[i];}//存储质因数
			t^1&&(s[++cnt]=t);//存储质因数
		}
		I bool IsGR(CI x,CI X)//暴力判断
		{
			for(RI i=1;i<=cnt;++i) if(Qpow(x,(X-1)/s[i],X)==1) return false;
			return true;
		}
		I void Sieve(CI l,CI r,CI X)//筛
		{
			static int T=0;RI i,j,p,t;++T;//初始化
			for(t=1;!IsGR(t,X);++t);for(i=1,p=t;i^X;++i) pos[p]=i,p=1LL*p*t%X;//暴力找到一个最小的原根，然后求指标
			for(i=1;i<=cnt;++i) for(j=s[i];j<X;j+=s[i]) vis[j]=T;//打标记
			for(i=l;i<=r;++i) F.writec(vis[pos[i]]^T?'g':'.');//输出
		}
	public:
		I void Solve()
		{
			RI n,i,l,r,X;for(L.Sieve(S),F.read(n);n;--n)
			{
				if((!F.read(l,r,X)&&(X=1515343657))||(X==998244353))//对于?赋值为1515343657
					for(Init(X-1),i=l;i<=r;++i) F.writec(IsGR(i,X)?'g':'.');//暴力
				else Init(X-1),Sieve(l,r,X);F.writec('\n');//筛
			}
		}
}GR;

    代码

    最后放一下完整代码：

    #include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define RL Reg LL
#define RU Reg ull
#define Con const
#define CI Con int&
#define CL Con LL&
#define CU Con ull&
#define I inline
#define W while
#define LL long long
#define ull unsigned long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define Gmin(x,y) (x>(y)&&(x=(y)))
using namespace std;
string op;
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I bool read(Ty& x) {x=0;W(!D) if(c=='?') return false;W(x=tn+(c&15),D);return true;}
		Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
		Ts I bool read(Ty& x,Ar&... y) {return read(x)&&read(y...);}
		Tp I void writeln(Con Ty& x) {write(x),pc('\n');}
		Tp I void read_with_X(Ty& x,CL X) {x=0;W(!D);W(x=(tn%X+(c&15))%X,D);}
		I void reads(string& x) {x="";W(isspace(c=tc()));W(x+=c,!isspace(c=tc())&&~c);}
		I void writec(Con char& x) {pc(x);}
		I void clear() {fwrite(FO,1,C,stdout),C=0;}
}F;
I void Qmul(LL& x,CL y,CL X) {RL k=(LL)((1.0L*x*y)/(1.0L*X)),t=x*y-k*X;t-=X;W(t<0) t+=X;x=t;}//快速乘
I LL Qpow(RL x,RL y,CL X) {RL t=1;W(y) y&1&&(Qmul(t,x,X),0),Qmul(x,x,X),y>>=1;return t;}//快速幂
class MillerRabin//MillerRabin判素数板子
{
	private:
		I bool Check(CL x,CI p)
		{
			if(Qpow(p%x,x-1,x)^1) return false;
			RL k=x-1,t;W(!(k&1))
			{
				if((t=Qpow(p%x,k>>=1,x))^1&&t^(x-1)) return false;
				if(!(t^(x-1))) return true;
			}return true;
		}
	public:
		I bool IsPrime(CL x) 
		{
			return !(x^2)||!(x^3)||(x&1&&x%3&&Check(x,2)&&Check(x,3));
		}
}MR;
class LineSiever//线性筛
{
	private:
		#define SZ 1000000
	public:
		int Pc,mu[SZ+5],P[SZ+5];
		I void Sieve(CI S)
		{
			for(RI i=(mu[1]=1,2),j;i<=S;++i)
				for(!P[i]&&(mu[P[++Pc]=i]=-1),j=1;j<=Pc&&1LL*i*P[j]<=S;++j)
					if(P[i*P[j]]=1,i%P[j]) mu[i*P[j]]=-mu[i];else break;
		}
}L;
class CommonPow19Solver//求解19^x
{
	public:
		I void Solve(CL X)//求解答案，X为模数
		{
			RI n;RL x;for(F.read(n);n;--n)
				F.read_with_X(x,X-1),F.writeln(Qpow(19,x,X));//读入时向X-1取模，然后快速幂
		}
}Common;
class OverFlowPow19Solver//求解溢出情况下19^x
{
	private:
		#define A 55244//开始循环的位置
		#define B 45699//循环周期
		#define X 998244353//模数
		int a[A+B+5];
	public:
		I void Solve()
		{
			RI n,i;RL x;for(a[0]=i=1;i<=A+B;++i) a[i]=19*a[i-1]%X;//打表
			for(F.read(n);n;--n) F.read(x),F.writeln(a[x<=A?x:(x-A)%B+A]);//输出答案
		}
		#undef X
}OverFlow;
class PrimeSolver//判断一段区间内每个数是否为质数
{
	public:
		I void Solve()
		{
			RI n;RL i,l,r;for(F.read(n);n;--n,F.writec('\n'))
				for(F.read(l,r),i=l;i<=r;++i) F.writec(MR.IsPrime(i)?'p':'.');//输出
		}
}Prime;
class MuSolver//求一段区间内每个数的μ值
{
	private:
		#define S 1000000
		#define C(x) ((x)?(~(x)?'+':'-'):'0')
		int g[S+5];ull v[S+5];
	public:
		I void Solve()
		{
			RI n,i,j,lim,len;RU x,y,l,r;for(L.Sieve(S),F.read(n);n;--n)
			{
				if(F.read(l,r),l<=S)//对于筛过的数，直接输出μ值
				{
					for(i=l,lim=min(r,S);i<=lim;++i) F.writec(C(L.mu[i]));
					if(F.writec('\n'),r<=S) continue;l=S+1;
				}
				for(len=r-l+1,i=len;i;--i) g[i]=v[i]=1;//初始化
				for(i=L.Pc;i;--i) for(j=(l+L.P[i]-1)/L.P[i]*L.P[i]-l+1;j<=len;j+=L.P[i])//枚举质数及其倍数
					(l+j-1)/L.P[i]%L.P[i]?g[j]&&(g[j]*=-1,v[j]*=L.P[i]):(g[j]=0);//统计μ值
				for(i=1;i<=len;++i) g[i]&&(i+l-1)^v[i]&&(MR.IsPrime(x=(i+l-1)/v[i])?//如果不为1
					g[i]*=-1:(y=sqrt(x),y*y==x)&&(g[i]=0)),F.writec(C(g[i]));//为质数则将μ值乘-1，为完全平方数则将μ值变为0，然后输出
				F.writec('\n');
			}
		}
		#undef S
}Mu;
class GRSolver//判断一段区间内每个数是否为给定质数的原根
{
	private:
		#define S 100000
		#define V 13123111
		int cnt,s[S+5],pos[V+5],vis[V+5];
		I void Init(CI x)//分解
		{
			RI i,t=x;for(cnt=0,i=1;1LL*L.P[i]*L.P[i]<=t;++i)
				if(!(t%L.P[i])) {s[++cnt]=L.P[i];W(!(t%L.P[i])) t/=L.P[i];}//存储质因数
			t^1&&(s[++cnt]=t);//存储质因数
		}
		I bool IsGR(CI x,CI X)//暴力判断
		{
			for(RI i=1;i<=cnt;++i) if(Qpow(x,(X-1)/s[i],X)==1) return false;
			return true;
		}
		I void Sieve(CI l,CI r,CI X)//筛
		{
			static int T=0;RI i,j,p,t;++T;//初始化
			for(t=1;!IsGR(t,X);++t);for(i=1,p=t;i^X;++i) pos[p]=i,p=1LL*p*t%X;//暴力找到一个最小的原根，然后求指标
			for(i=1;i<=cnt;++i) for(j=s[i];j<X;j+=s[i]) vis[j]=T;//打标记
			for(i=l;i<=r;++i) F.writec(vis[pos[i]]^T?'g':'.');//输出
		}
	public:
		I void Solve()
		{
			RI n,i,l,r,X;for(L.Sieve(S),F.read(n);n;--n)
			{
				if((!F.read(l,r,X)&&(X=1515343657))||(X==998244353))//对于?赋值为1515343657
					for(Init(X-1),i=l;i<=r;++i) F.writec(IsGR(i,X)?'g':'.');//暴力
				else Init(X-1),Sieve(l,r,X);F.writec('\n');//筛
			}
		}
}GR;
int main()
{
	if(F.reads(op),op=="1_998244353") Common.Solve(998244353);
	else if(op=="1?") Common.Solve(1145141);
	else if(op=="1?+") Common.Solve(5211600617818708273);
	else if(op=="1wa_998244353") OverFlow.Solve();
	else if(op=="2p") Prime.Solve();else if(op=="2u") Mu.Solve();else GR.Solve();
	return F.clear(),0;
}
    • 1

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

    信息

    ID
    4267
    时间
    2000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 31ms