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

打表万岁！！！

#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]

话说刚开始我是想打表的，因为一看样例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;

做了我好久啊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.

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

jj中加*

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: 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.

暴力直接判真的能过=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;
很好奇筛法的做法...

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

#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要提前处理出来，不能再循环中直接求，不然会超时

新改的程序，保证一次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.

一模一样的程序，第一次超时，第二次过了
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.

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

由于 B-A

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无限制。

数据MS没10^8那么大

这题怎么这种通过率

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.

朴素

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.

打表才是硬道理！！

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