大佬们,看看我的思路对不对,以空间换时间
查看原帖
大佬们,看看我的思路对不对,以空间换时间
560868
CiXuKun楼主2022/11/7 16:36
枚举p,q判断p*q==n&&(p-1)(q-1)+1==e*d O(kp^2)-> 超时
枚举p,q=n/p,在判断 便读入边判断 O(kp) -> 可能超时
如果是先读入存起来在计算呢?
struct{
	long long a,b,c;
}a[(int)1e5+10];
空间复杂度O(1e5*3),3MB
时间复杂度O(k+p) ->接近O(n)
以时间换空间

2022/11/7 16:36
加载中...