scau13校赛17115 ooxx numbers 暴力打表+因数和

最新推荐文章于 2021-01-17 14:58:42 发布

keepcoral

最新推荐文章于 2021-01-17 14:58:42 发布

阅读量604

点赞数

分类专栏：暴力数学

本文链接：https://blog.csdn.net/keepcoral/article/details/79863867

版权

暴力同时被 2 个专栏收录

8 篇文章

订阅专栏

数学

1 篇文章

订阅专栏

17115 ooxx numbers

时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题语言: G++;GCC

Description

a number A called oo number of a number B if the sum of all As factor is the number B.
(A,B) is a pair of ooxx numbers if A is the oo number of B and B is the oo number of A.
Now i want to find how many pairs of ooxx numbers in [1,n]

输入格式

there are many cases in the input.
for each line there is a number n. ( 1 <= n <= 5000000 )

输出格式

for each n, output the numbers of pairs of ooxx numbers in [1,n]

输入样例

300
1300

输出样例

1
2

提示

hits 
220=1+2+4+71+142=284,
284=1+2+4+5+10+11+20+22+44+55+110=220。
220 and 280 is a pair of ooxx numbers.

作者

admin

500w*500w单纯直接暴力就算打表也是很痛苦的一件事，所以还是用点数学方法。

我们以前学过效率比较高的素数筛选

for(i=2;i<=n;i++)

for(j=2*i;j<=n;j++)

pri[j]=1 这就是直接筛选素数

那么i其实就是因子，因此我们可以利用类似的思想去处理因数和

for(i=1;i<=n;i++)

for(j=2*i;j<=n;j++)

dig[j]+=i;

i一定是j的因子，因此数字dig[j]加上i就是它的因子和，一直循环到500w，就可以得到1-500w的因子和了，然后去处理一下，吧两个互等的提取出来，然后记住，要排序！！！因为它可能会出现小的在后面的情况。

#include <iostream>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#define mod 1000000007
using namespace std;
int dig[5000020];
int a[100][2];
int b[100]= {284
             ,1210
             ,2924
             ,5564
             ,6368
             ,10856
             ,14595
             ,18416
             ,76084
             ,66992
             ,71145
             ,87633
             ,88730
             ,124155
             ,139815
             ,123152
             ,153176
             ,168730
             ,176336
             ,180848
             ,203432
             ,202444
             ,365084
             ,389924
             ,430402
             ,399592
             ,455344
             ,486178
             ,514736
             ,525915
             ,669688
             ,686072
             ,691256
             ,712216
             ,652664
             ,783556
             ,796696
             ,863835
             ,901424
             ,980984
             ,1125765
             ,1043096
             ,1099390
             ,1189150
             ,1292570
             ,1438983
             ,1286744
             ,1340235
             ,1483850
             ,1486845
             ,1464592
             ,1747930
             ,1749212
             ,1598470
             ,2062570
             ,1870245
             ,2090656
             ,2429030
             ,2941672
             ,2874064
             ,3077354
             ,2928136
             ,2947216
             ,3716164
             ,3721544
             ,3892670
             ,4300136
             ,4006736
             ,4314616
             ,4488910
             ,4445050
            };
int main()
{
    /*int i,j;
    for(i=1; i<=5000000; i++)
    {
        for(j=2*i; j<=5000000; j+=i)
        {
            dig[j]+=i;
        }
    }
    int t=0;
    for(i=2; i<=5000000; i++)
    {
        j=dig[i];
        if(dig[i]==-1||j>5000000) continue;
        if(dig[j]==i&&i!=j)
        {
            a[t][0]=i;
            a[t][1]=j;
            t++;
            dig[j]=-1;
            dig[i]=-1;
            printf("%d  %d\n",a[t-1][0],a[t-1][1]);
        }
    }*/
    //t=71;
    int n;
    sort(b,b+71);
    while(~scanf("%d",&n))
    {
        int i;
    for(i=0;i<=70;i++)
    {
        if(n<b[i])
        {
            break;
        }
    }
    if(i==71) printf("71\n");
    else printf("%d\n",i);
    }

}