月老的烦恼(1)
- 描述
-
月老最近遇到了一个很棘手的问题,就是“剩男”“剩女”急速增长,而自己这边又人手不足导致天天都得加班。现在需要你来帮助月老解决这个问题,牵红绳的规则很简单:每个男生都一个编号n(1<=n<=500000),编号n的因数之和就是要牵线的女生的编号。
如20的因子是:1,2,4,5,10
- 输入
- 输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000). 输出
- 对于每组测试数据,请输出一个代表输入编号N男生的另一半的编号. 样例输入
-
321012
样例输出 -
1816
下面的代码超时了,是我一开始的简单朴素的想法,想着把n开根号之后,可以缩短时间,降低时间复杂度,不过还是too young too simple 了,貌似一般的方法都不能顺利通过,可能是测试的数据量太大的缘故。
1 #include2 #include 3 #include 4 using namespace std; 5 6 int main(){ 7 int t; 8 scanf("%d",&t); 9 while(t--){10 int n;11 scanf("%d",&n);12 long long res=1;13 for(int i=2;i
AC写法:这是在讨论区摘录的写法,打表法!
1 #include2 #include 3 long sum[500005]; 4 5 int main(){ 6 int t,n,i,j; 7 8 //整个的思想就是打表,将500000内所有的结果全部计算出来,备用 9 for(i=1;i<=500000;i++) 10 for(j=1;j*i<=500000;j++)11 sum[i*j]+= i; //这一步的i*j将“因子”这个因素全部考虑进去了 12 13 scanf("%d",&t);14 while(t--){15 scanf("%d",&n);16 printf("%ld\n",sum[n]-n);17 }18 return 0;19 }
另一种写法:
1 2 #include3 const int A=500001; 4 int a[A]={ 0,0}; 5 int main(){ 6 //每个数都有因子:1 7 for(int i =2;i <= A/2; i++) 12 for(int j = i*2;j