题目1491：求1和2的个数

题目描述：

给定正整数N，函数F(N)表示小于等于N的自然数中1和2的个数之和，例如：1,2,3,4,5,6,7,8,9,10序列中1和2的个数之和为3，因此F(10)=3。输入N，求F(N)的值，1=<N<=10^100(10的100次方)若F(N)很大，则求F(N)mod20123的值。

输入：

输入包含多组测试数据，每组仅输入一个整数N。

输出：

对于每组测试数据，输出小于等于N的自然数中1和2的个数之和，且对20123取模。

样例输入：

10
11

样例输出：

3
5

见编程之美 1的数目

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

char s[110];


int ston(int a,int b){
 int x = 0;
 for(int i = a;i <= b;i++){
  x = x * 10 + s[i];
  x = x % 20123;
 }
 return x;
}
int factor(int n){
 int x = 1;
 while(n){
  x *= 10;
  x = x % 20123;
  n--;
 }
 return x;
}

int main()
{
 while(scanf("%s",s)){
  int len = strlen(s);
  for(int i = 0; i < len; i++)
   s[i] -= '0';
  int sum = 0;
  for(int i = 0; i < len; i++){
   int highnum = ston(0,i - 1);
   int lowernum = ston(i + 1,len - 1);
   int fat = factor(len - i - 1);
   switch(s[i]){
   case 0 :
    sum += (2 * highnum * fat) % 20123;
    break;
   case 1:
    sum += (2 * highnum * fat + lowernum + 1) % 20123;
    break;
   case 2:
    sum += ((2 * highnum + 1) * fat + lowernum + 1) % 20123;
    break;
   default:
    sum += (2 * (highnum + 1) * fat) % 20123;
   }
   sum %= 20123;
  }
  cout << sum << endl;
 }
 return 0;
}