HOW TO EXTRACT ALL THE FACTORS OF A LARGE NUMBER QUICKLY?(FASTER THAN O(n))

ding

朴素算法已经 O(sqrt(n)) 了

有 rho 启发式方法可以在期望 O(sqrt(sqrt(n))) 时间内输出一个因子（但不保证能出解）

这个题只能搜索吧。。。。反正我是搜索的。。。。。

总有一个点TLE

ssxyh帮忙看一下

var a,b:array[1..50]of longint；

d,m,o,i:integer；

ab,by,p,j:qword；

function gcd(x,y:longint):longint；

begin

if y=0 then gcd:=x else gcd:=gcd(y,x mod y)；

end；

begin

readln(d)；

for i:=1 to d do read(a[i])；

readln；

readln(m)；

for i:=1 to m do read(b[i])；

ab:=a[1]；

for i:=2 to d do ab:=ab*a[i] div gcd(ab,a[i])；

by:=b[1]；

for i:=2 to m do by:=gcd(by,b[i])；

if (by<ab)or(by mod ab<>0) then

begin

writeln(0)；

exit；

end；

if by=ab then

begin

writeln(1)；

exit；

end；

p:=by div ab；

o:=0；

j:=0；

while j<p do

begin

inc(j)；

if p mod j=0 then inc(o)；

end；

writeln(o)；

end.

朴素的模拟能拿高分．．．

我搜索的是质因子。。。。和你搜索的方向不同。。

貌似我开始明白了...