FurinaOI Round 1 题解 - 洛谷保存站

### A

考虑先构造一个 $2\times \frac{2n}{\operatorname{lowbit}(n)}$ 的矩阵 $a$，第一行前一半放 $1$，后一半放 $0$，第二行全放 $0$。

接下来进行 $\log_2(\operatorname{lowbit}(n))$ 次如下操作：

- 设矩阵 $a$ 有 $n'$ 行 $m'$ 列，则将其扩展到 $2n'$ 行 $2m'$ 列。

- 对于所有 $1\le i\le n',1\le j \le m'$，将 $a_{i+n',j}$ 和 $a_{i,j+m'}$ 赋值为 $a_{i,j}$，将 $a_{i+n',j+m'}$ 赋值为 $1-a_{i,j}$。

操作结束后，矩阵的第 $i$ 行即为第 $i$ 个二进制数。

证明：首先初始的矩阵满足条件。

- 每一次操作结束后，若选择 $1\le i,j \le n'$，则 $a_i,a_j$ 两个数的异或值的 $1$ 个数相当于复制之前的 $a_i,a_j$ 的异或值 $1$ 的个数的两倍，也就是新的矩阵列数的一半 $m'$；

- 若选择 $1\le i \le n',n'+1\le j \le 2n'$，则 $a_i,a_j$ 的前 $m'$ 位是完全相同的，后面则完全不同，所以异或起来 $1$ 的个数就是 $m'$。

- 若选择 $n'+1\le i,j \le 2n'$，则 $a_i,a_j$ 的异或值 $1$ 的个数相当于操作之前的 $a_{i-n'}$ 和 $a_{j-n'}$ 的异或值 $1$ 的个数加上两者分别取反以后的异或和，也就是 $\frac{m'}2+(m'-\frac{m'}2)=m$。

综上，这种方法可以构造出合法的答案。

```cpp
#include<bits/stdc++.h>
#define N 2005
using namespace std;
int n,a[N][N];
int main(){
	cin>>n;
	int nn=2,mm=(n*2)/(n&-n);
	for(int i=1;i<=mm/2;++i)a[1][i]=1;
	while(n%2==0){
		n/=2;
		for(int i=1;i<=nn;++i){
			for(int j=1;j<=mm;++j){
				a[i+nn][j]=a[i][j+mm]=a[i][j];
				a[i+nn][j+mm]=!a[i][j];
			}
		}
		nn*=2;mm*=2;
	}
	for(int i=1;i<=nn;++i){
		for(int j=1;j<=mm;++j)putchar(a[i][j]+'0');cout<<'\n';
	}
	return 0;
}
```

### B

~~题目质量极低的一道题，不管了反正不是我出的题。~~

有一种想法是压位高精度，有一位选手极限卡常通过了，我们预期正常写能得 50pts。

压位高精度虽然时间慢，但是空间很少，我们现在需要找一个空间大时间快的东西和它拼起来。所以考虑 FFT，像快速幂一样处理，时间复杂度是 $T(n)=T(\frac{n}2)+n\log n=O(n \log n)$。

我不确定有没有只写 FFT 压进空间限制的方法，反正我没有做到，所以就写了个 $n\log n$ 空间的。

```cpp
#include<bits/stdc++.h>
#define N 3000005
using namespace std;
const double pi=acos(-1.0);
struct cp{
	double x,y;
	cp(){x=y=0;};
	cp(double x2,double y2){
		x=x2;y=y2;
	}
};
cp operator+(cp a,cp b){
	return cp(a.x+b.x,a.y+b.y);
}
cp operator-(cp a,cp b){
	return cp(a.x-b.x,a.y-b.y);
}
cp operator*(cp a,cp b){
	return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
int rev[N],len[N];
vector<cp>lz[21];
string s,t;
void FFT(int n,vector<cp>&a,int op){
	for(int i=0;i<n;++i){
		if(i<rev[i])swap(a[i],a[rev[i]]);
	}
	for(int len=1;len<=n/2;len*=2){
		cp u(cos(pi/len),op*sin(pi/len));
		for(int i=0;i<=n-len*2;i+=len*2){
			cp w(1,0);
			for(int j=0;j<len;++j){
				cp x=a[i+j],y=w*a[i+j+len];
				a[i+j]=x+y,a[i+j+len]=x-y;
				w=w*u;
			}
		}
	}
}
int C,sum[N],nowlen,n;
vector<cp> mul(vector<cp>a,vector<cp>b,int n,int m){
	int qwq=0,k=1;
	vector<cp>ans;
	while(k<=n+m)++qwq,k*=2;
	for(int i=1;i<k;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(qwq-1));
	while(a.size()<k+1)a.push_back(cp{0,0});
	while(b.size()<k+1)b.push_back(cp{0,0});
	FFT(k,a,1);FFT(k,b,1);
	for(int i=0;i<=k;++i)ans.push_back(a[i]*b[i]);
	FFT(k,ans,-1);
	for(int i=0;i<=n+m+10;++i)sum[i]=0;
	for(int i=0;i<=n+m;++i)sum[i]=(int)(ans[i].x/k+0.01);
	for(int i=0;i<=n+m;++i){
		sum[i+1]+=sum[i]/10;sum[i]%=10;
	}
	int len=n+m;
	while(sum[len+1]){
		++len;sum[len+1]+=sum[len]/10;sum[len]%=10;
	}
	vector<cp>rans(len+1);
	for(int i=0;i<=len;++i)rans[i].x=sum[i];nowlen=len;
	while(!sum[nowlen])--nowlen;
	return rans;
}
vector<cp>ans;
long long c[N];
const int X=1e9;
int main(){
	cin>>C>>n;
	if(C%2){
		int len=2;
		c[2]=(1ll<<(n&31))/X,c[1]=(1ll<<(n&31))%X;
	    for(int i=1;i<=(n>>5);++i){
	        for(int j=1;j<=len;++j)c[j]<<=32;
	        for(int j=1;j<=len;++j)c[j+1]+=c[j]/X,c[j]%=X;
	        while(c[len]>0)++len;
	    }
	    while(c[len]==0)--len;
	    printf("%lld",c[len]);
	    for(int i=len-1;i>=1;--i)printf("%09lld",c[i]);
	    return 0;
	}
	lz[0].push_back(cp{2,0});ans.push_back(cp{1,0});
	for(int i=1;i<20;++i){
		lz[i]=mul(lz[i-1],lz[i-1],nowlen,nowlen);len[i]=nowlen;
	}
	nowlen=0;
	for(int i=0;i<20;++i){
		if((n>>i)&1){
			ans=mul(ans,lz[i],nowlen,len[i]);
		}
	}
	for(int i=0;i<=nowlen;++i)sum[i]=int(ans[i].x+1e-6);
	while(!sum[nowlen])--nowlen;
	for(int i=nowlen;i>=0;--i)putchar(sum[i]+'0');
	return 0;
}
```

### C

考虑对式子进行变形：

$$p(a+b)=qab$$

$$q^2ab-pq(a+b)=0$$

$$q^2ab-pq(a+b)+p^2=p^2$$

$$(qa-p)(qb-p)=p^2$$

考虑用 Pollard-rho 对 $p$ 分解质因数得到 $p^2$ 的质因数分解，然后暴力枚举判断，时间复杂度 $O(p^{0.25}+d(p^2))$。你发现 $10^{36}$ 内的数因数最多只有 $10^8$ 量级，所以不会超时。

```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
mt19937 rnd(time(0));
int rr[15]={2,3,5,7,11,13,17,19,23,29,31,37},testtime=12;
long long n,T,zhi[55],t,p,q,lz[55],num[55],yy,ans;
int gcd(int x,int y){
	if(x%y==0)return y;
	return gcd(y,x%y);
}
int abs(int x){
	return x>0?x:-x;
}
__int128 qpow(__int128 x,int y,int mod){
	__int128 ans=1;
	while(y){
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
bool Mr(int n){
	if(n<2)return 0;
	if(n==2||n==3)return 1;
	int d=n-1,r=0;
	while(d%2==0)++r,d/=2;
	for(int i=0;i<testtime;++i){
		int a=rr[i]%(n-2)+2,x=qpow((__int128)a,d,n);
		if(x==1||x==n-1)continue;
		for(int j=0;j<r-1;++j){
			x=(__int128)x*x%n;
			if(x==n-1)break;
		}
		if(x!=n-1)return 0;
	}
	return 1;
}
int Pr(int n){
	int s=0,t=0,val=1,c=rnd()%(n-1)+1;
	for(int i=1;;i*=2,s=t,val=1){
		for(int j=1;j<=i;++j){
			t=(__int128)t*t+c;t%=n;
			val=(__int128)val*abs(t-s)%n;
			if(j%127==0){
				int qwq=gcd(val,n);
				if(qwq>1)return qwq;
			}
		}
		int qwq=gcd(val,n);
		if(qwq>1)return qwq;
	}
}
void calc(int n){
	if(n<=ans||n<2)return;
	if(Mr(n)){
		zhi[++t]=n;return;
	}
	int d=n;
	while(d>=n)d=Pr(n);
	calc(d);calc(n/d);
}
void dfs(signed dep,int x){
	if(x+p<0)return;
	if(dep>yy){
		int y=(__int128)p*p/x;
		if((x+p)%q==0&&x+p>0&&(y+p)%q==0&&y+p>0)++ans;
		return;
	}
	dfs(dep+1,x);
	for(signed i=1;i<=num[dep];++i)x*=lz[dep],dfs(dep+1,x);
}
signed main(){
	cin>>p>>q;
	calc(p);
	sort(zhi+1,zhi+t+1);
	for(int i=1;i<=t;++i){
		if(zhi[i]!=zhi[i-1])lz[++yy]=zhi[i],num[yy]=1;
		else ++num[yy];
	}
	for(int i=1;i<=yy;++i)num[i]*=2;
	dfs(1,1);dfs(1,-1);
	cout<<ans;
	return 0;
}
```

正在渲染内容...