“大数处理“

题目描述：输入数字a,n,计算[a+aa+..+aaaaaa..aaa(n个a)]mod1000000007;

想法：主要利用了模运算的有关规律使得每一个数字计算时都不会溢出。同时将每个a进行分组，有n个a，（n-1）个a0.(0的个数视a的位数定）

代码：

#include<stdio.h>
long long ComputeBit(long long a)
{
  long long i=10;
  while(a/10)
    {
  i*=10;
  a=a/10;
    }
  return i;
}//
long long Mode(long long dishu,long long zhishu)
{
  long long i=0;
  long long moshu=1;
  while(i<zhishu)
    {
    moshu=moshu*dishu%1000000007;
    i++;
    }
  return moshu;
}
int main()
{
  long long sum=0,a,Bit,i,base;
  while(scanf("%lld%lld",&a,&n))
    {
      sum=0;
      Bit=ComputeBit(a);
      for(i=0;i<n;i++)
	{
	  base=(a*Mode(Bit,i))%1000000007;
	  sum=(sum+((n-i)*base)%1000000007)%1000000007;
	}
      printf("%lld",sum);
    }
}

上述算法复杂度较高在1000000,1000000这样的数据时运行时间过长。同学H有了下面的做法。事实证明很多东西需要精心打算

#include <stdio.h>

#define M 1000000007u

int main()
{
    unsigned a,n;
    unsigned b;
    unsigned long long sum;

    while (scanf("%u%u",&n) )
      {
	b=1;
	sum=0;
    unsigned t = a;
    do {
        b*=10;
        t/=10;
    } while (t);

    unsigned long long term = a;
    while (n) {
        sum += term;
        term = (term*b+a)%M;
        n--;
    }

    printf("%un",sum%M);
      }

    return 0;
}

题目的改进：如果最后的结果不取模值

想到的方法。将数字转化为字符串输出，根据a确定亲的进制，从新进制的低位开始算，每次的结果转化为倒序字符串入Stack，然后输出stack中的元素。