华师一附中OI组

标题: 把1-99的数写成一排，设为X=12345678910111212**99，求X%997 [打印本页]
作者: admin    时间: 2020-2-10 14:39
标题: 把1-99的数写成一排，设为X=12345678910111212**99，求X%997
此题的基本思想是类似单精度除法，和那个天使的起誓类似。我们把1-99的数字装到一个数组，作为单精度除法的被除数，让它按位去除以997，最后得到的余数就是。
如何装入数组呢？我们用最直观的方法，先把1-9作为一位数装入，再把10-99作为两位数装入。这里可以写一个循环，里面判断一位数还是两位数，也可以分开写成两个循环。

  1. #include <iostream>
  2. using namespace std;
  3. int i,p,x;
  4. int a[210];
  5. int main()
  6. {
  7.         for (p=1; p<=9; p++) a[p]=p;  ///一位数加进数组
  8.         p=9;for (i=10; i<=99; i++)
  9.         {
  10.                 int x1=i/10,x2=i%10;///分离十位个位
  11.                 a[p+1]=x1,a[p+2]=x2;///加进数组
  12.                 p=p+2; ///p记录最后一个位置
  13.         }
  14.         int maxp=p;/// 记录最后一个位置
  15.         ///输出检查 for(p=1; p<=maxp; p++) cout<<a[p];
  16.         ///类似单精度除法
  17.         x=0;for (p=1; p<=maxp; p++)
  18.         {
  19.                 x=10*x+a[p];  ///被除数
  20.                 a[p]=x/997;///商，此题其实没有必要记录
  21.                 x=x%997;///余数
  22.         }
  23.         cout<<x;
  24.         return 0;
  25. }
复制代码

一起处理也可以写成如下
  1. p=1;for (i=1; i<=99; i++)
  2.         {
  3.                 if (i<=9)
  4.                 {a[p]=i;p++;}///一位数处理
  5.                 else  ///两位数处理
  6.                 {
  7.                         int x1=i/10,x2=i%10;///分离十位个位
  8.                         a[p+1]=x1,a[p+2]=x2;///加进数组
  9.                         p=p+2; ///p记录最后一个位置
  10.                 }
  11.         }
复制代码



答案是 896
作者: admin    时间: 2020-2-10 14:41
但是楼上的做法不够精简，被除数我们完全没有必要装进数组保存，直接按规律生成就是，商也没有必要保存。而且，我们还先一次处理完一位数，然后循环一次处理两位，数学可以证明这样是没有问题的。

  1. #include <iostream>
  2. using namespace std;
  3. int i,x;
  4. int main()
  5. {
  6.         x=123456789%997;///一位数的余数
  7.         for (i=10; i<=99; i++)
  8.         {
  9.                 x=x*100+i;
  10.                 x=x%997;
  11.         }
  12.         cout<<x;
  13.         return 0;
  14. }
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2