hdu5832 A water problem (大数求余)

素颜马尾好姑娘i 2022-09-25 06:19 157阅读 0赞

hdu5832 A water problem (大数求余):[http://acm.hdu.edu.cn/showproblem.php?pid=5832][http_acm.hdu.edu.cn_showproblem.php_pid_5832]

题目描述：

<table style="font-family:'Times New Roman'; word-wrap:break-word"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="word-wrap:break-word; width:980px; margin-top:10px">  
     <span style="margin-right:20px"><a href="http://acm.hdu.edu.cn/contests/contest_list.php" style="color:red; text-decoration:none" rel="nofollow">合训练的同学们~&nbsp;</a><br> </span>  
    </div> </td> 
  </tr> 
  <tr> 
   <td align="center"> <h1 style="color:rgb(26,92,200)">A water problem</h1> <strong><span style="font-family:Arial; font-size:12px; color:green">Time Limit: 5000/2500 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/65536 K (Java/Others)<br> Total Submission(s): 365&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 201<br> </span></strong><br> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Problem Description 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      Two planets named Haha and Xixi in the universe and they were created with the universe beginning. 
     <br> 
     <br> There is&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:1.113em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:1.044em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.701em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">73</span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.708em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>&nbsp;days in Xixi a year and&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:1.598em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:1.529em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.701em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">137</span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.708em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>&nbsp;days in Haha a year.&nbsp; 
     <br> 
     <br> Now you know the days&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.974em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.905em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.493em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math-italic">N<span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; overflow:hidden; height:1px; width:0.073em"></span></span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.5em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>&nbsp;after Big Bang, you need to answer whether it is the first day in a year about the two planets. 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      There are several test cases(about&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.558em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.558em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.701em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">5</span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.708em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>&nbsp;huge test cases). 
     <br> 
     <br> For each test, we have a line with an only integer&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:4.511em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:4.372em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.701em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math-italic">N<span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; overflow:hidden; height:1px; width:0.073em"></span></span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">(</span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">0</span><span style="display:inline; position:static; border:0px; padding:0px 0px 0px 0.281em; margin:0px; vertical-align:0px; font-family:MathJax_Main">≤</span><span style="display:inline; position:static; border:0px; padding:0px 0px 0px 0.281em; margin:0px; vertical-align:0px; font-family:MathJax_Math-italic">N<span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; overflow:hidden; height:1px; width:0.073em"></span></span><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">)</span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.708em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.354em; overflow:hidden; width:0px; height:1.146em"></span></span> </span>, the length of&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.974em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0.905em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.493em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Math-italic">N<span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; overflow:hidden; height:1px; width:0.073em"></span></span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.5em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>&nbsp;is up to&nbsp; 
     <span style="color:rgb(136,136,136)"></span> 
     <span style="display:inline; word-spacing:normal; word-wrap:normal; white-space:nowrap; float:none; direction:ltr; max-width:none; max-height:none; min-width:0px; min-height:0px; border:0px; padding:0px; margin:0px"> <span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:4.164em"><span style="display:inline-block; position:relative; border:0px; padding:0px; margin:0px; vertical-align:0px; width:4.026em; height:0px; font-size:14.4200000762939px"><span style="position:absolute; border:0px; padding:0px; margin:0px; vertical-align:0px; top:-2.701em; left:0.003em"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px"><span style="display:inline; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; font-family:MathJax_Main">10000000</span></span><span style="display:inline-block; position:static; border:0px; padding:0px; margin:0px; vertical-align:0px; width:0px; height:2.708em"></span></span></span><span style="display:inline-block; position:static; border-width:0px 0px 0px 0.004em; border-left-style:solid; border-color:initial; padding:0px; margin:0px; vertical-align:-0.068em; overflow:hidden; width:0px; height:0.861em"></span></span> </span>. 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left">
      For the i-th test case, output Case #i: , then output "YES" or "NO" for the answer. 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
       
      <div style="font-family:'Courier New',Courier,monospace">
       
        
       10001
0
333
      
       
      </div></pre> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:'Times New Roman'; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
       
      <div style="font-family:'Courier New',Courier,monospace">
       
        
       Case #1: YES
Case #2: YES
Case #3: NO
      
       
      </div></pre> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

题目大意：

输入一个数n，n为一个大数，若n既是73的倍数又是137的倍数，则输出YES，否则输出NO。

题目分析：

由于73和137都是质数，所以，若n为73\*137的倍数，则输出YES，否则输出NO。但是由于n为大数，10的7次方以内的数，则直接开10的7次方的char数组进行输入，还要把char数组中的内容对应到int数组中，会内存超限，同样用java语言交的话，也会内存超限，为了不超限，有两种处理的方法。

代码实现一：

#include <cstdio>
    #include <cstring>
    
    const int N=1000010;
    typedef long long LL ;
    LL a[N]={0};
    char a1[N*10];
    
    int main()
    {
        int i,j,k;
        LL d,b;
        int T=0;
        while(scanf("%s",a1)!=-1)
        {
            T++;
            //if (strcmp(a1,"0")==0) {printf("Case #%d: YES\n",T);continue;}
            d=0;
            k=strlen(a1);
            //printf("kkk%d\n",k);
            for(i=0,j=0; i<k; j++)
            {
                if (i+10<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+((LL)a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000+(LL)(a1[k-i-6]-'0')*100000+(LL)(a1[k-i-7]-'0')*1000000+(LL)(a1[k-i-8]-'0')*10000000+(LL)(a1[k-i-9]-'0')*100000000+(LL)(a1[k-i-10]-'0')*1000000000;
                    i+=10;
                }
                else if (i+10>k && i+9<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000+(LL)(a1[k-i-6]-'0')*100000+(LL)(a1[k-i-7]-'0')*1000000+(LL)(a1[k-i-8]-'0')*10000000+(LL)(a1[k-i-9]-'0')*100000000;
                    i+=9;
                }
                else if (i+9>k && i+8<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000+(LL)(a1[k-i-6]-'0')*100000+(LL)(a1[k-i-7]-'0')*1000000+(LL)(a1[k-i-8]-'0')*10000000;
                    i+=8;
                }
                else if (i+8>k && i+7<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000+(LL)(a1[k-i-6]-'0')*100000+(LL)(a1[k-i-7]-'0')*1000000;
                    i+=7;
                }
                else if (i+7>k && i+6<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000+(LL)(a1[k-i-6]-'0')*100000;
                    i+=6;
                }
                else if (i+6>k && i+5<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000+(LL)(a1[k-i-5]-'0')*10000;
                    i+=5;
                }
                else if (i+5>k && i+4<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100+(LL)(a1[k-i-4]-'0')*1000;
                    i+=4;
                }
                else if (i+4>k && i+3<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10+(LL)(a1[k-i-3]-'0')*100;
                    i+=3;
                }
                else if (i+3>k && i+2<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0')+(LL)(a1[k-i-2]-'0')*10;
                    i+=2;
                }
                else if (i+2>k && i+1<=k)
                {
                    a[j]=(LL)(a1[k-i-1]-'0');
                    i++;
                }
            }
    //        for(int i=j-1; i>=0; i--)
    //        {
    //            printf("%I64d ",a[i]);
    //        }
    //        printf("\n");
            for(i=j-1; i>=0; i--)
            {
                d=d*10000000000+a[i];
                d=d%10001;
            }
            if (d==0) printf("Case #%d: YES\n",T);
            else printf("Case #%d: NO\n",T);
        }
        return 0;
    }

代码实现二：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int mod=10001;
    
    char str[10000100];
    
    int main()
    {
        long long sum;
        int casenum=1;
        while(scanf("%s",str)!=EOF)
        {
            sum=0;
            int len=strlen(str);
            for(int i=0;i<len;i++)
            {
                sum=sum*10+(str[i]-'0');
                sum=sum%mod;
            }
            if(sum==0)
            {
                printf("Case #%d: YES\n",casenum++);
            }
            else
            {
                printf("Case #%d: NO\n",casenum++);
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5832]: http://acm.hdu.edu.cn/showproblem.php?pid=5832