题解

135 条题解

  • 2
    @ 2015-08-14 22:10:51

    P1216亲和数Accepted
    记录信息
    评测状态 Accepted
    题目 P1216 亲和数
    递交时间 2015-08-14 22:10:35
    代码语言 C++
    评测机 VijosEx
    消耗时间 1603 ms
    消耗内存 520 KiB
    评测时间 2015-08-14 22:10:37
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 93 ms, mem = 516 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 516 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 516 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 516 KiB, score = 10
    测试数据 #4: Accepted, time = 109 ms, mem = 516 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 512 KiB, score = 10
    测试数据 #6: Accepted, time = 296 ms, mem = 512 KiB, score = 10
    测试数据 #7: Accepted, time = 46 ms, mem = 520 KiB, score = 10
    测试数据 #8: Accepted, time = 546 ms, mem = 516 KiB, score = 10
    测试数据 #9: Accepted, time = 468 ms, mem = 516 KiB, score = 10
    Accepted, time = 1603 ms, mem = 520 KiB, score = 100
    代码
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    int main()
    {
    int a,b;
    scanf("%d%d",&a,&b);
    int ans_=0;
    for(int i=a;i<=b;i++)
    {
    int ans=1;
    for(int j=2;j*j<=i;j++)
    {
    if(i%j==0)
    ans+=j+i/j;
    }
    if(ans<=i)continue;
    int ans2=1;
    for(int j=2;j*j<=ans;j++)
    {
    if(ans%j==0)
    ans2+=j+ans/j;
    }
    if(ans2==i)
    ans_+=1;
    }
    printf("%d",ans_);
    }

  • 2
    @ 2009-02-15 09:59:52

    打表万岁!!!

    #include

    using namespace std;

    int list[100]={220,1184,2620,5020,6232,10744,12285,

    17296,63020,66928,67095,69615,79750,

    100485,122265,122368,141664,142310,

    171856,176272,185368,196724,280540,

    308620,319550,356408,437456,469028,

    503056,522405,600392,609928,624184,

    635624,643336,667964,726104,802725,879712,

    898216,947835,998104,1077890,

    1077890,1154450,1280565,1392368,1511930,1798875,2082464,

    4238984,5459176,

    6329416,7677248,9363584,10254970,13921528,16137628,50997596,

    52695376,56055872,56512610,56924192,58580540,59497888,63560025,

    63717615,66595130,66854710,67729064,67738268,68891992,71015260,

    71241830,72958556,73032872,74055952,74386305,74769345,75171808,

    75226888,78088504,78447010,79324875,80422335,82633005,83135650,

    84521745,84591405,86158220,87998470,88144630,89477984,90437150,91996816,

    93837808,95629904,95791430,96304845,97041735};

    main () {

    int x,y,i,n=0;

    cin>>x>>y;

    for (i=0;i=x&&list[i]

  • 0
    @ 2017-02-06 21:46:00

    话说刚开始我是想打表的,因为一看样例200-1200只有2个数,那么打个表应该不难。。。
    不废话了,亲和数这个题千万不要想复杂了,耗时间的地方其实就是求[A,B]区间内的正因数和,类比于素数的求法,需要知道的是这样一个公理:
    ##对于一个给定正实数x,如果x≡0(mod i),那么x≡0(mod x/i)。##
    这样一来我们可以将区间放缩,由[1,n]缩小到[1,√n],每次如果x≡0(mod i),SUM+=i+n/i;值得一说的是,区间到达√n的时候,需要进行特判。
    #如果x≡0(mod √n),那么需要和只需要加一个√n就好了。#
    思路简单,代码不难,核心代码如下:
    int i=2,SUM=1;//从2开始可以减少1次判断,然后SUM要从1开始
    for(i=1;i*i<n;i++)//区间缩小
    if(n%i==0)
    SUM+=i+n/i;
    if(i*i==n)
    return SUM+i;//这里特判
    return SUM;

  • 0
    @ 2016-03-27 15:18:54

    做了我好久啊var
    i,j,a,b,s,s2,sum:longint;
    begin
    read(a,b);
    sum:=0;
    for i:=a to b do
    begin
    s:=1;
    for j:=2 to trunc(sqrt(i)) do
    if i mod j=0 then
    begin
    s:=s+j;
    s:=s+i div j;
    end;
    if sqrt(i)=trunc(sqrt(i)) then s:=s-trunc(sqrt(i));
    s2:=1;
    for j:=2 to trunc(sqrt(s)) do
    if s mod j=0 then
    begin
    s2:=s2+j;
    s2:=s2+s div j;
    end;
    if sqrt(s)=trunc(sqrt(s)) then s2:=s2-trunc(sqrt(s));
    if (s2=i) and (s>i) then inc(sum);
    end;
    writeln(sum);
    end.

  • 0
    @ 2015-08-04 08:41:39

    #include<cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    int qiu(int x)
    {
    int i,s;
    int t=int(sqrt(double(x+1)));
    s=1;
    for(i=2;i<=t;i++)
    {
    if(x%i==0) s+=i+x/i;
    }
    if(t*t==x) s=s-t;
    return s;
    }
    int main()
    {
    int i,sa,sb,A,B,a,b,ans=0;
    scanf("%d%d",&a,&b);
    for(i=a;i<=b;i++)
    {
    A=i;
    sa=qiu(A);
    B=sa;
    sb=qiu(B);
    if(sb==A && A<B) ans++;
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2015-02-02 10:52:00

    jj中加*

  • 0
    @ 2015-02-02 10:51:38

    var
    a,b,n,s,k,x,y:int64;
    i,j:longint;
    begin
    readln(a,b);
    s:=0;
    for i:=a to b do
    begin
    x:=0;
    y:=0;
    for j:= 1 to trunc(sqrt(i)) do
    begin
    if (i mod j=0) then
    begin
    x:=x+j;
    if (j*j<>i) then x:=x+trunc(i/j);
    end;
    end;
    x:=x-i;
    if x>i then
    begin
    for j:= 1 to trunc(sqrt(x)) do
    begin
    if (x mod j=0) then
    begin
    y:=y+j;
    if (j*j<>x) then y:=y+trunc(x/j);
    end;
    end;
    y:=y-x;
    if (i=y)and(i<x) then inc(s);
    end;
    end;
    writeln(s);
    end.

  • 0
    @ 2015-02-02 10:49:28

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 124 ms, mem = 744 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 740 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 744 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 744 KiB, score = 10

    测试数据 #4: Accepted, time = 140 ms, mem = 744 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 740 KiB, score = 10

    测试数据 #6: Accepted, time = 421 ms, mem = 740 KiB, score = 10

    测试数据 #7: Accepted, time = 46 ms, mem = 744 KiB, score = 10

    测试数据 #8: Accepted, time = 702 ms, mem = 740 KiB, score = 10

    测试数据 #9: Accepted, time = 608 ms, mem = 740 KiB, score = 10

    Accepted, time = 2071 ms, mem = 744 KiB, score = 100

    代码
    var
    a,b,n,s,k,x,y:int64;
    i,j:longint;
    begin
    readln(a,b);
    s:=0;
    for i:=a to b do
    begin
    x:=0;
    y:=0;
    for j:= 1 to trunc(sqrt(i)) do
    begin
    if (i mod j=0) then
    begin
    x:=x+j;
    if (j*j<>i) then x:=x+trunc(i/j);
    end;
    end;
    x:=x-i;
    if x>i then
    begin
    for j:= 1 to trunc(sqrt(x)) do
    begin
    if (x mod j=0) then
    begin
    y:=y+j;
    if (j*j<>x) then y:=y+trunc(x/j);
    end;
    end;
    y:=y-x;
    if (i=y)and(i<x) then inc(s);
    end;
    end;
    writeln(s);
    end.

  • 0
    @ 2015-01-31 15:15:04

    暴力直接判真的能过=w=
    计算因数和的时候

    int u=(int)sqrt(k);
    for(int i=2;i<=u;i++)
    if(k%i==0) res+=i+k/i;
    if(u*u==k) res-=u;
    很好奇筛法的做法...

  • 0
    @ 2014-12-29 10:37:15

    Block code

    /*
    Author: Traveller_C
    PROG: vijos 1216
    DATE: 2014.12.29
    */

    #include <iostream>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    const int maxn = 100000005;
    const int maxm = 100005;

    int a, b;
    int ans = 0, sum1 = 0, sum2 = 0;

    void init()
    {
    scanf("%d%d", &a, &b);
    }

    void doit()
    {
    int i;
    for (i = a; i <= b; i ++){
    sum1 = 0, sum2 = 0;
    for (int j = 1; j * j <= i; j ++)
    if (i % j == 0){
    sum1 += j;
    if (j != 1) sum1 += i / j;
    }
    if (sum1 <= i) continue;
    for (int j = 1; j * j <= sum1; j ++)
    if (sum1 % j == 0){
    sum2 += j;
    if (j != 1) sum2 += sum1 / j;
    }
    if (i == sum2){
    ans ++;
    }
    }
    printf("%d\n", ans);
    }

    int main()
    {
    init();
    doit();
    //system("pause");
    return 0;
    }

  • 0
    @ 2014-12-20 19:53:38

    #include<iostream>
    #include<cmath>
    using namespace std;
    int main()
    {
    int sum,ans1,ans2,a,b,i,j,k,n,t;
    cin>>a>>b;
    sum=0;
    for (i=a; i<=b; ++i)
    {
    ans1=1;
    ans2=1;
    n=trunc(sqrt(i));
    for (j=2; j<=n; ++j)
    if (i%j==0) ans1=ans1+i/j+j;
    if (ans1<=i) continue;
    t=trunc(sqrt(ans1));
    for (j=2; j<=t; ++j)
    if (ans1%j==0)
    {
    ans2=ans2+ans1/j+j;
    if (ans2>i) continue;
    }
    if (i==ans2) ++sum;
    }
    cout<<sum;
    return 0;

    }
    c++的要注意 sqrt要提前处理出来,不能再循环中直接求,不然会超时

  • 0
    @ 2013-08-27 17:04:50

    新改的程序,保证一次AC
    var
    a,b,n,s,k,x,y:int64;
    i,j:longint;
    begin
    readln(a,b);
    s:=0;
    for i:=a to b do
    begin
    x:=0;
    y:=0;
    for j:= 1 to trunc(sqrt(i)) do
    begin
    if (i mod j=0) then
    begin
    x:=x+j;
    if (j*j<>i) then x:=x+trunc(i/j);
    end;
    end;
    x:=x-i;
    if x>i then
    begin
    //writeln(x);
    for j:= 1 to trunc(sqrt(x)) do
    begin
    if (x mod j=0) then
    begin
    y:=y+j;
    if (j*j<>x) then y:=y+trunc(x/j);
    end;
    end;
    y:=y-x;
    //writeln(y);
    if (i=y)and(i<x) then inc(s);
    end;
    end;
    writeln(s);
    end.

  • 0
    @ 2013-08-26 18:17:05

    一模一样的程序,第一次超时,第二次过了
    var
    a,b,n,s,k,x,y:int64;
    i,j:longint;
    begin
    readln(a,b);
    s:=0;
    for i:=a to b do
    begin
    x:=0;
    y:=0;
    for j:= 1 to trunc(sqrt(i)) do
    begin
    if (i mod j=0) then
    begin
    x:=x+j;
    if (j*j<>i) then x:=x+trunc(i/j);
    end;
    end;
    x:=x-i;
    //writeln(x);
    for j:= 1 to trunc(sqrt(x)) do
    begin
    if (x mod j=0) then
    begin
    y:=y+j;
    if (j*j<>x) then y:=y+trunc(x/j);
    end;
    end;
    y:=y-x;
    //writeln(y);
    if (i=y)and(i<x) then inc(s);
    end;
    writeln(s);
    end.

  • 0
    @ 2012-07-23 21:38:21

    注意:A和B只是指x的范围,而不是y的范围;

    由于 B-A

  • 0
    @ 2010-07-27 15:21:33

    var

    i,j,k,a,b,sum,t,x,s,ans:longint;

    c:array[0..1000000]of longint;

    begin

    readln(a,b);

    t:=(a div 100000)*100000;

    s:=a-t;

    for i:=a to b do

    begin

    x:=i;sum:=0;

    for j:=2 to trunc(sqrt(x))do

    if x mod j=0 then sum:=sum+j+x div j;

    inc(sum);

    c:=sum;{由于区间长度较小先把[a,b]的所有数的因子和求出来,并且离散化处理}

    end;

    ans:=0;

    for i:=s to s+b-a do

    if i+tx的要求} then

    begin

    x:=i+t;sum:=0;

    for j:=2 to trunc(sqrt(c[i]))do{算数对(x,y)中的y的因子和能否为x}{注意y不要预先处理,因为的范围不知道}

    begin

    if c[i] mod j=0 then sum:=sum+j+c[i] div j;

    if sum>x then break;{这是很有用的剪枝:当大于x时直接break}

    end;

    inc(sum);

    if (sum=x)then

    inc(ans);

    end;

    writeln(ans);

    end.

    分析:现将[a,b]中每个数的因子和求出来,并离散化(若>10^5就减到10^5以内)开一个数组记录,最后在求每一个数的

    因子和(即y)的因子和,然后在判断。

    注意点:题目中只对x的限制在【a,b】中,而y无限制。

  • 0
    @ 2010-07-05 23:52:17

    数据MS没10^8那么大

    这题怎么这种通过率

  • 0
    @ 2010-03-14 17:45:36

    program p1216;

    var a,b,k,x,s1,s2,i:longint;

    begin

    readln(a,b);

    k:=0;

    for x:=a to b do

    begin

    s1:=1;

    for i:=2 to trunc(sqrt(x))-1 do

    if x mod i=0 then

    s1:=s1+i+(x div i);

    if trunc(sqrt(x))*trunc(sqrt(x))=x then inc(s1,trunc(sqrt(x)));

    if s1>x then

    begin

    s2:=1;

    for i:=2 to trunc(sqrt(s1))-1 do

    if s1 mod i=0 then

    s2:=s2+i+(s1 div i);

    if trunc(sqrt(s1))*trunc(sqrt(s1))=x then inc(s2,trunc(sqrt(s1)));

    if s2=x then inc(k);

    end;

    end;

    writeln(k);

    end.

  • 0
    @ 2009-11-08 08:01:11

    朴素

    program aa;

    var

    i,j,a,b,s,s2,sum:longint;

    begin

    read(a,b);

    sum:=0;

    for i:=a to b do

    begin

    s:=1;

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

    if i mod j=0 then

    begin

    s:=s+j;

    s:=s+i div j;

    end;

    if sqrt(i)=trunc(sqrt(i)) then s:=s-trunc(sqrt(i));

    s2:=1;

    for j:=2 to trunc(sqrt(s)) do

    if s mod j=0 then

    begin

    s2:=s2+j;

    s2:=s2+s div j;

    end;

    if sqrt(s)=trunc(sqrt(s)) then s2:=s2-trunc(sqrt(s));

    if (s2=i) and (s>i) then inc(sum);

    end;

    writeln(sum);

    end.

  • 0
    @ 2009-11-05 11:37:38

    打表才是硬道理!!

  • 0
    @ 2009-10-31 19:29:25

    var

    a,b,m,n,i,j,x,k,c:longint;

    function work(y,z:longint):longint;

    begin

    n:=0;

    j:=0;

    for i:= 1 to y-1 do

    begin

    if y mod i=0 then

    begin

    n:=n+(y div i);

    end;

    if n

信息

ID
1216
难度
5
分类
模拟 点击显示
标签
(无)
递交数
2685
已通过
891
通过率
33%
被复制
6
上传者