var

i,j,x0,y0,k:longint;

function can(i,j:longint):boolean;

var a,b,t:longint;

begin

a:=i; b:=j; t:=j mod i;

while t0 do

begin j:=i; i:=t; t:=j mod i; end;

if(i=x0)and(a*b div i=y0)then

can:=true else can:=false;

end;

begin

read(x0,y0); k:=0;

for i:=x0 to y0 do

for j:=i+1 to y0 do

if can(i,j) then

inc(k);

write(2*k);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

智慧的方法虽然令人羡慕，可是不智慧的方法也能秒杀……

辗转相除过的……

program kl;

var

a,b,c,e,h,l,j:longint;

f:array[1..100]of longint;

d,k,i,g:byte;

begin

read(a,b);c:=a; e:=1; g:=0; i:=0;

while c

var

i,j,x0,y0,k,s,t1,p:longint;

a:array[1..1000000]of longint;

b:array[1..1000000]of 0..1;

procedure gy(x,y:longint);

var m:longint;

begin

m:=x mod y;

if m=0 then t1:=y

else gy(y,m);

end;

begin

readln(x0,y0);

fillchar(b,sizeof(b),0);

s:=0;k:=0;p:=0;

for i:=x0 to y0 do

if y0 mod i=0 then

begin

inc(k);

a[k]:=i;

end;

for i:=1 to k-1 do

for j:=i+1 to k do

begin

gy(a[i],a[j]);

if (t1=x0)and(a[i]*a[j] div t1=y0)and(b[a[j]]=0)and(b[a[i]]=0) then

begin

inc(s);

if a[i]=j then p:=1;

b[j]:=1;b[a[i]]:=1;

break;

end;

end;

if p=1 then write(s*2-1)

else write(s*2);

end.

= = 本来以为可以扫水题

可是 提交了3次 都WA了

终于。。

没办法 继续悲剧下去

搜索范围 [x0,y0 div x0],统计满足条件的个数，最后再乘以2，即顺序可以调换。

枚举p,q并规定p

编译通过...

├ 测试数据 01：答案正确... 88ms

├ 测试数据 02：答案正确... 88ms

├ 测试数据 03：答案正确... 88ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：440ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

#include"stdio.h"

int yue(long k1,long k2)

{ long k3;

k3=k1%k2;

while(k3!=0)

{ k1=k2;

k2=k3;

k3=k1%k2;

}

if(k2!=1) return 0;

else return 1;

}

int main()

{ long i=1,j=2,k,m,n,q,w,num=0;

scanf("%ld%ld",&q,&w);

while(q*i

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

（接近o（n div 4）的快速算法）；

var

i,j,k,p,q,x0,y0,t,s:longint;

begin

readln(x0,y0);

if (y0 mod x0)0 then begin writeln(0);halt;end;{不符合条件直接退出}

t:=y0 div x0;

{求非公共部分的质因子}

for i:=2 to t div 2{剪枝:(50%)一个数的除他本身以外的所有质因子只可能出现在：2~这个数DIV 2之间} do

begin

if t mod i0 then continue;{剪枝1：（50%以上）不是他的因子直接退出}

if ((i2)and(i mod 2=0))or((i mod 3=0)and(i3))or((i mod 5=0)and(i5))or((i7)and(i mod 7=0)) then continue;{剪枝2：（40%）不可能是质因子退出}

inc(k);

for j:=2 to trunc(sqrt(i)) do{可能是质因子，进行判断}

if i mod j=0 then begin dec(k);break;end;

end;

inc(k);

for i:=2 to trunc(sqrt(t)) do

if t mod i=0 then begin dec(k);break;end;{判断这个数本身是不是他的质因子}

s:=1 shl k;

writeln(s);

end.

{公式：gcd（x，y）*lcm（x,y）=x*y;

lcm（x,y)/ gcd（x，y）=x与y两数的非公共部分，设为gg。(证明见最下1).

求出gg的质因子个数k,在求出质因子个数所有可能的子集数为：2^k(证明见最下2) ;输出2^k 即可}

{1:

设 gcd(x,y)*m=x;

gcd(x,y)*n=y;（m，n既互质）

则：lcm(x,y)=gcd(x,y)*m*n;

lcm(x,y)*gcd(x,y)=gcd(x,y)*m*n*gcd(x,y)

=x*y;

lcm(x,y)/gcd(x,y)=m*n,m*n为x与y两数的非公共部分，所以lcm(x,y)/gcd(x,y)=x与y两数的非公共部分}

{2：求出m*n的质因子个数为gg:

gg个质因子设为集合s：我们只要把集合s拆分为两个不同的集合a,b即可,集合s所有可能的拆分种数既是所求。

两个集合a,b只要有一个集合确定了，另一个集合就确定了（因为b=s-a，a，b一一对应），则集合s所有可能的拆分种数=集合a所有的种数，

所以我们只考虑集合a所有的种数，为2^k个。

证明：当集合中含1个元素时，它的子集为：2个（包括空集），=2^1个；

当集合中含2个元素时， 它的子集为：4个（包括空集），=2^2个；

当集合中含3个元素时， 它的子集为：8个（包括空集），=2^3个；

......

当集合中含K个元素时，它的子集为：2^k个；}

{举例：s=[2,3,5]

s所有的拆分：

a=[] b=[1,2,3];

a=[1] b=[2,3];

a=[2] b=[1,3];

a=[3] b=[1,2];

a=[1,2] b=[3];

a=[1,3] b=[2];

a=[2,3] b=[1];

a=[1,2,3] b=[]; }

注意

优化

避免超时

goon1023

#include

int t =0;

long x0,y0;

void s(int &a,int &b)

{

int t;

t=a;

a=b;

b=t;

}

int gy(int p,int q)

{

if(p>q)

s(p,q);

if(q%p==0)

{

return p;

}

else

{

return gy(p,q%p);

}

}

int main()

{

cin>>x0>>y0;

for(int i=x0;i

可能数据比较弱吧

否则O(x*y)的算法怎么过

var

x,y,i,j,t:longint;

function gcd(a,b:longint):longint;

begin

if b=0 then exit(a);

gcd:=gcd(b,a mod b);

end;

begin

readln(x,y); t:=0;

if x=y then begin writeln(1); halt; end;

for i:=1 to y do

for j:=1 to y do

if i*j=x*y then if gcd(i,j)=x then inc(t);

writeln(t);

end.

#include

int hcf(int u,int v)

{int t,r;

if(v>u)

{t=u;u=v;v=t;}

while((r=u%v)!=0)

{return(v);}

int lcd(int u;int v;int h)

{return(u*v/h);}

main()

{int u,v,h,l;

scanf("%d%d",&u,$v);

h=hcf(u,v);

printf("zhuida=%d\n",h);

l=lcd(u,v,h)

printf("zhuixiao=%d\n",l);}

第一次交没做优化，第四点超时

第二次加了几句，秒杀了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var x,y,p,q,c,d:longint;

function maxgys(a,b:longint):longint;

begin

if b=0 then exit(a)

else exit(maxgys(b,a mod b));

end;

begin

read(x,y);

if x=y then

begin

write(1);

halt;

end;

c:=0;

for p:=x to y do

if (p mod x=0)and(y mod p=0) then //为优化而加的语句

for q:=p+1 to y do

if (q mod x=0)and(y mod q=0) then //为优化而加的语句

begin

d:=maxgys(p,q);

if (d=x)and(p*q div d=y) then c:=c+1;

end;

write(c*2);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 712ms (虽然用了很长时间，但还是AC了！^_^)

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：712ms

program p1131(input,output);

var zs,a,b,x,y:longint;

function gy(p,q:longint):longint;

var c,i:longint;

begin

if p

太暴力了...

惨不忍睹...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var i,j,x0,y0,e:longint;

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

begin

if y=0 then gcd:=x

else gcd:=gcd(y,x mod y);

end;

begin

readln(x0,y0);

for i:=1 to y0 do

for j:=1 to y0 do

if i*j=y0*x0 then

if gcd(i,j)=x0 then inc(e);

write(e);

end.

var i,x,y,m,k,q:longint;

a:array[1..10000,1..2]of longint;

procedure dg(m:longint);

var i:longint;

begin

i:=1;

for i:=1 to m do

if m mod i=0 then

begin

inc(k);

a[k,1]:=i;

a[k,2]:=m div i;

end;

end;

begin

readln(x,y);

if y mod x0 then begin write('0'); exit; end;

m:=y div x;

dg(m);

for i:=1 to k do

begin

a:=a*x;

a:=a*x;

if ((a mod a=0)and(a

program dsa;

var s,x,y,i,j:longint;

function pp(p,q:longint):boolean;

var

i:longint;

l:boolean;

begin

l:=true;

for i:=2 to p do

if (p mod i=0) and (q mod i=0) then l:=false;

pp:=l;

end;

begin

read(x,y);

if y mod x0 then write(0)

else if x=y then write(1)

else

begin

for i:=1 to y div x do

for j:=1 to y div x do

if (i*j=y div x) and (pp(i,j)) then

s:=s+1;

write(s);

end;

end.

农夫山泉