193 条题解

  • 0
    @ 2009-08-15 18:08:10

    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.

  • 0
    @ 2009-08-14 12:55:03

    编译通过...

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

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

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

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

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

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

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

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

    辗转相除过的……

  • 0
    @ 2009-08-13 11:32:41

    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

  • 0
    @ 2009-08-13 10:19:59

    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.

  • 0
    @ 2009-08-12 20:09:53

    = = 本来以为可以扫水题

    可是 提交了3次 都WA了

    终于。。

    没办法 继续悲剧下去

  • 0
    @ 2009-08-09 10:48:51

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

    枚举p,q并规定p

  • 0
    @ 2009-08-08 11:05:16

    编译通过...

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

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

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

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

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

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

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

  • 0
    @ 2009-08-06 23:14:17

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-08-06 20:11:11

    ├ 测试数据 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=[]; }

  • 0
    @ 2009-08-06 19:46:00

    注意

    优化

    避免超时

  • 0
    @ 2009-08-05 12:30:31

    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

  • 0
    @ 2009-07-30 16:29:22

    可能数据比较弱吧

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

  • 0
    @ 2009-07-29 21:34:21

    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.

  • 0
    @ 2009-08-09 08:27:01

    #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);}

  • 0
    @ 2009-07-26 21:34:07

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

    第二次加了几句,秒杀了

    编译通过...

    ├ 测试数据 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.

  • 0
    @ 2009-07-24 16:32:40

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-07-20 16:02:06

    太暴力了...

    惨不忍睹...

  • 0
    @ 2009-07-20 13:46:31

    编译通过...

    ├ 测试数据 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.

  • 0
    @ 2009-07-19 22:32:41

    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

  • 0
    @ 2009-07-16 15:10:23

    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.

    农夫山泉

最小公倍数和最大公约数问题

信息

ID
1131
难度
4
分类
其他 | 数学搜索 | 枚举 点击显示
标签
递交数
7297
已通过
2964
通过率
41%
被复制
24
上传者