亲密数字（number）

Question

我这超时了请问大家这怎样更简便
【运行时限】：3秒。

假设两个不同的正整数A和B是亲密数字，那么有如下的性质：①整数A的全部真约数（包括1，不包括A本身）之和等于B；②整数B的全部真约数（包括1，不包括B本身）之和等于A。

举个例子，对于220和284这一对亲密数字来说：

220的全部真约数有：1+2+4+5+10+11+20+22+44+55+110 = 284
284的全部真约数有：1+2+4+71+142 = 220
请你编写一个程序，从键盘输入正整数X和Y(2≤X≤Y≤32767)，在屏幕分行输出X和Y之间所有的成对亲密数字，中间用空格隔开，同时要保证小数在前，大数在后。

输入输出格式
输入
输入一行，包含两个正整数X和Y(2≤X≤Y≤32767)，中间用空格隔开。

输出
输出多行，对应多组亲密数字，每行包含两个正整数，即X和Y之间所有的成对亲密数字，中间用空格隔开。

样例
输入1
2 1000
输出1
220 284
时间及空间限制
1s, 256MB.
我编的代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,i,j,s=0,s2=0;
    cin>>x>>y;
    for(i=x;i<=y;i++)
    {
        s=0;s2=0;
        for(j=1;j<i;j++)
        {
        if(i%j==0)
        {
            s=s+j;
        }
            
        }
    
        if(s>=x&&s<=y)
        {
            for(j=1;j<s;j++)
            {
                if(s%j==0)
                {
                    s2=s2+j;
                }
            }
            if(s2==i&&i<s)
            {
                cout<<i<<" "<<s<<endl;
            }
        }
    }
}

求回复。

Answer 1

求约数和可以降到O(sqrt(n))的级别。

更新思路：枚举A，先求A的约数和tmp，然后求tmp的约数和t2，若t2=A，则A和tmp是亲密数。

优化后代码如下：

#include <bits/stdc++.h>
using namespace std;
int x, y;
int main() {
    scanf("%d%d", &x, &y);
    for (int i = x; i <= y; i++) {
        int tmp = 1, lm1 = sqrt(i);
        for (int j = 2; j <= lm1; j++)
            if (i % j == 0)
                tmp += j + i / j;
        if (lm1 * lm1 == i) tmp -= lm1;
        if (i >= tmp) continue;
        int t2 = 1, lm2 = sqrt(tmp);
        for (int j = 2; j <= lm2; j++)
            if (tmp % j == 0)
                t2 += j + tmp / j;
        if (lm2 * lm2 == tmp) t2 -= lm2;
        if (t2 == i) printf("%d %d\n", i, tmp);
    }
    return 0;
}

经测试，时间复杂度大约为O(n*sqrt(n))，32768稳过。