正睿寒假Day1(20200203) T2 数论题【前缀最小逆元】

程序员文章站 2022-05-12 23:31:15

...

题目描述：

题目分析：

逆元可以看做一个伪随机序列，前 $\sqrt p$ 个数的逆元的最小值期望可以缩小到 $O(\sqrt p)$ 级别。

所以当 $p\le10^9$ 时可以枚举前 $\sqrt p$ 个数，求出最小逆元，再枚举逆元求出对应的位置，时间复杂度期望 $O(\sqrt p)$ 。
具体实现时也可以从小到大枚举 $i$ ，记录逆元的最小值 $mn$ ，如果 $inv[i]<mn$ 则计入答案，当 $inv[i]<i$ 时就可以退出了（将此时的所有答案翻转过来也是答案，它是对称的，比如答案有 $2 ~~(p+1)/2$ ，那么必然有 $(p+1)/2 ~~2$ ）

由于多组数据，当 $p$ 过大的时候直接枚举会超时，观察能够形成前缀最小值的 $i*f(i)=kp+1$ ，因为当 $i$ 达到 $\sqrt p$ 时 $f(i)$ 期望已经 $<\sqrt p$ 了，所以 $k$ 不会很大。

我们可以枚举 $k$ ，然后将 $kp+1$ 用Pollard_Rho算法分解因数求出所有的 $i*f(i)$ ，最后将其按 $i$ 排序，检验 $f(i)$ 是否是前缀最小，输出即可。时间复杂度为 $O(\sum_{k}k*((kp+1)^{0.25}+\sigma(kp+1)))$
具体实现时取 $k=40$ 即可通过（我最慢的一个点跑了994ms）。
也有不设具体的 $k$ 值的方法，假设已经枚举到了 $k$ ，已经分解出的因数为 $i_1,i_2...,i_m$ ，如果 $(i_x-1)*\text{inv}[i_{x-1}]\le kp+1$ ，说明在 $i_{x-1}$ 到 $i_x$ 之间不可能还有解，如果对于所有的 $x$ 这个不等式都成立（以及 $i_m$ 和 $(p+1)/2$ ），那么说明当前枚举到的 $k$ 已经足够了。~~直接设k=40多好啊~~

Code：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int T;
namespace solve1{
	const int N = 3000005;
	int inv[N],q[N],cnt;
	void main(LL p){
		cnt=0,inv[0]=inv[1]=1;int mn=p;
		for(int i=2;;i++){
			inv[i]=(p-p/i)*inv[p%i]%p;
			if(inv[i]<i) break;
			if(inv[i]<mn) mn=inv[i],q[++cnt]=i;
		}
		printf("%d\n",cnt?cnt*2-(q[cnt]==inv[q[cnt]]):0);
		for(int i=1;i<=cnt;i++) printf("%d %d\n",q[i],inv[q[i]]);
		for(int i=cnt-(q[cnt]==inv[q[cnt]]);i>=1;i--) printf("%d %d\n",inv[q[i]],q[i]);
	}
}
namespace solve2{
	LL pr[65],base[6]={2,3,7,61,19260817};int pc;
	inline LL mul(LL a,LL b,LL p){LL r=a*b-(LL)((long double)a/p*b+0.5)*p;return r<0?r+p:r;}
	inline LL Pow(LL a,LL b,LL p){
		LL s=1; for(;b;b>>=1,a=mul(a,a,p)) if(b&1) s=mul(s,a,p);
		return s;
	}
	bool Miller_Rabin(LL n){
		for(int i=0;i<5;i++) if(n==base[i]) return 1; else if(n%base[i]==0) return 0;
		LL d=n-1;int k=0;
		while(!(d&1)) d>>=1,k++;
		for(int i=0;i<5;i++){
			LL x=Pow(base[i],d,n),y;
			for(int i=1;i<=k&&x!=1;i++,x=y)
				if((y=mul(x,x,n))==1&&x!=n-1) return 0;
			if(x!=1) return 0;
		}
		return 1;
	}
	LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
	LL Rho(LL n,int c){
		LL x=rand()%n+1,y=x,d=1,q=1;
		for(int k=1;;k<<=1,y=x,q=1){
			for(int i=1;i<=k&&d==1;i++){
				q=mul(abs((x=(mul(x,x,n)+c)%n)-y),q,n);
				if(!(i&127)) d=gcd(q,n);
			}
			if(d>1||(d=gcd(q,n))>1) return d==n?Rho(n,c+1):d;
		}
	}
	void Pollard(LL n){
		while(!(n&1)) n>>=1,pr[++pc]=2;
		if(n==1) return;
		if(Miller_Rabin(n)) {pr[++pc]=n;return;}
		LL p=Rho(n,3);
		Pollard(p),Pollard(n/p);
	}
	pair<LL,LL>ans[3000005]; int tot,cnt;
	LL d[60005];int dc;
	void main(LL p){
		tot=cnt=0;
		for(int k=1;k<=40;k++){
			LL t=k*p+1,pw;
			pc=0,Pollard(t),sort(pr+1,pr+pc+1);
			d[dc=1]=1,pr[pc+1]=0;
			for(int i=1,j,e;i<=pc;i=j){
				for(j=i+1,e=1;pr[i]==pr[j];j++,e++);
				for(int j=dc,k;j>=1;j--)
					for(k=1,pw=pr[i];k<=e;k++,pw*=pr[i]) d[++dc]=d[j]*pw;
			}
			for(int i=2;i<=dc;i++) if(d[i]<p&&t/d[i]<p) ans[++tot]=(make_pair(d[i],t/d[i]));
		}
		sort(ans+1,ans+1+tot); LL mn=p;
		for(int i=1;i<=tot;i++)
			if(ans[i].second<mn) mn=ans[i].second,ans[++cnt]=ans[i];
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;i++) printf("%lld %lld\n",ans[i].first,ans[i].second);
	}
}
int main()
{
	scanf("%d",&T);LL p;
	while(T--){
		scanf("%lld",&p);
		if(p<=1e9) solve1::main(p);
		else solve2::main(p);
	}
}