HDU 1215--七夕节

ゝ一世哀愁。 2022-08-25 05:27 168阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td> <h1>七夕节</h1> </td> 
  </tr> 
  <tr> 
   <td> <p><font>Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)</font></p> </td> 
  </tr> 
  <tr> 
   <td> <p><font>Total Submission(s): 2628 Accepted Submission(s): 986</font></p> </td> 
  </tr> 
  <tr> 
   <td><br></td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Problem Description 
    </div> 
    <div>
      七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!" 
     <br> 人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下: 
     <br> 
     <br>  
     <img src="http://simg.sinajs.cn/blog7style/images/common/sg_trans.gif" alt="HDU&nbsp;<wbr>1215--七夕节" title="HDU&nbsp;<wbr>1215--七夕节">  
     <br> 数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6. 
     <br> 你想知道你的另一半吗? 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Input 
    </div> 
    <div>
      输入数据的第一行是一个数字T(1&lt;=T&lt;=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1&lt;=N&lt;=500000). 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Output 
    </div> 
    <div>
      对于每组测试数据,请输出一个代表输入数据N的另一半的编号. 
     <br> 
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Input 
    </div> 
    <div>
      3 
     <br> 2 
     <br> 10 
     <br> 20 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      Sample Output 
    </div> 
    <div>
      1 
     <br> 8 
     <br> 22 
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
  </tr> 
 </tbody> 
</table>

当时看到数据范围只有500000，于是就想到暴力求解。结果这一暴力就出问题了，OJ毫不留情的给了个TLE。想一想，从结果看来，应该是测试实例很多的原因，于是，这直接导致全场悲剧，AC率极低。遇到TLE情况，无非就是优化算法，这其中就有一种常用的方法，就是先把所有的结果给储存起来，这样虐时就不是问题了。先注意到任何一个数的任何一个因子是其约数，这个道理大家都懂，但真正注意到的人就少了。其实利用这个性质这道题解决了，即开一个a\[500000\]的数组，筛选法，双层循环进行累加。为了缩减time，第一层从i=2开始，第二层从第j=i+i开始,依次a\[j\]+=i进行累加，最后输出时对每个因子和加一就可以了，这样就达到了储存因子和的目的。代码:

\#include  
\#include  
\#include  
int main()  
\{  
int \*sfactor,i,j,n,t;  
sfactor=(int\*)malloc(500001\*sizeof(int));  
memset(sfactor,0,500001\*sizeof(int));  
for(i=2;i<=250000;i++)  
for(j=i+i;j<500001;j+=i)  
sfactor\[j\]+=i;  
scanf("%d",&t);  
while(t--)  
\{  
scanf("%d",&n);  
printf("%d\\n",sfactor\[n\]+1);  
\}  
return 0;  
\}