Question

一道超时的c++问题，求大神提供处理方法

#include <iostream>
using namespace std;
int main()
{
int a=10;
long long n,d;
while(cin>>n)

{
if(n==-1) break;
else {
int c=1;
for(int i=0;i<n;i++)
{c*=a;}
d=0;
for(int a=1;a<=c;a++)
{
d+=a;
}
}
cout<<d<<endl; }

return 0;
}
题目描述
在1011题中大家已经解决了谷学长的疑问，成功的使他重新振作起来。不过最近谷学长又遇到了更麻烦的问题，为了使他不再低迷，你能帮帮他吗？
题目是这样的：计算SUM(n) = 1 + 2 + 3 + ... + 10^n。满足n<=100 000。
输入
输入包含多组数据，每组数据一行，包括一个整数n(n<=100 000)。当n=-1时输入终止。

输出
对于每个n输出相应的和。
样例输入
1
2
-1

样例输出
55
5050

上面是我编的程序，可是提示超时，球大神帮忙！！！！

Answer 1

老大，10^n在n很大的时候，比如上限100000时是个什么概念？1后边有10万个0， 假设CPU的执行++的速度是10G，也就是10*10^9=10^10， 则要计算完需要10^(100000-10)秒，一年才不到4*10^7，所以在宇宙湮灭之前都不要想算完啦。

当然，按你的代码还不至于老是执行不完，原因是在c*=a时当n>10时会多次溢出。

得改算法：
注意到1+2+...+n=n(n+1)/2
当n=10^k时， n(n+1)/2= 5*10^(k-1)*(10^k+1)
以数位的形式来看： 50...050...0， 即结果中的各位上只有0和5，且5只出现两次，并将0分割为两半，两半0的个数一样，都为k-1个。

因此对本题无需计算，直接输出即可，不过要注意当输入的n=0时，需要输出的是1，不满足之前讨论。

追问

对于题目n<=100000,怎么搞

追答

void print(int n)
{
    if(n==0) printf("1");
    else
    {
        for(int j=0; j<2; j++)
        {
            printf("5");
            for(int i=n; i>1; i--) printf("0");
        }
    }
    printf("\n");
}

对任意的n<=100000，都可以用类似上述的办法输出。 所以你可以新写一个类似的print函数，对每个输入的n都调用该函数，或者直接将print的逻辑放到你原来while中的else里面， 同时去掉原else中的代码以及后边的cout语句。

类似有时间要求的题目最好不用cin和cout，相比而言scanf和printf的速度要快得多。

追问

scanf 和printf完全不会- -

追答

囧rz， 没看过C语言，直接学得C++？
那就把printf都换成cout好了，其中除了最后的printf("\n")换成cout<<endl;外，其余的都换成cout<<0;或者cout<<5;或者cout<<1;分别表示输出一个0，或5或1.