请学过ACM的朋友对下面的简单程序提出修改建议

中国可爱小牛

只是简单学习C++，但我是从来没有学过ACM的，因此问的问题可能很可笑，所以还请多多包涵.......
据说著名数学家高斯小时候通过仔细观察发现 1 + 2 + 3 + ... + 99 + 100 的值是 5050. 本题对于给定的正整数 n, 请计算 1 + 2 + 3 + ... + (10^n-1) + 10^n 的值.
Input
有多个测试用例. 每个测试用例是一个不超过 100000 的正整数 n. 输入直至没有数据为止.
Output

在一行上输出 1 到 10n 的累加和.
Sample Input
1
2
Sample Output
55
5050
下面是我的程序，程序可以运行，结果也对。但问题在于测试用例，我设计得不合理。但不知道如何改.......
#include<iostream>
using namespace std;
int main()
{
    int m;
    int sum=1,k;//用整型去定义sum是不对的，考虑过字符型，但对它的使用不熟悉.....

    while(cin>>m)
  {
  
      for(int i=0;i<m;i++)
    {
           
            sum*=10;
    }            
                     
            k=(1+sum)*sum/2;
  }      
  cout<<k<<endl;
   
   return 0;
}
在 n 个相异物品中选出 k 个物品的方法数叫做组合数, 记为 C(n,k). 这个数有一个简洁的公式: n!/(k!(n-k)!). 利用这个公式立即有 C(n,k) = C(n,n-k). 遗憾的是, 这个公式并不方便用于计算. 组合数有许多计算方法, 利用分数可以递推地计算:



C(n,k) = (n/k)*C(n-1,k-1), 其中 0 < k ≤ n, C(n,0) = 1.

也就是

C(n,k) = (n/k)*(n-1/k-1)*...*((n-k+2)/2)*((n-k+1)/1)

本题对于给定的 n, k, 请计算 C(n,k).

Input

有多个测试用例. 每个测试用例是两个整数 n, k ( 0 ≤ k ≤ n < 231), 且 n > 0. 输入直至没有数据为止.

Output

对于每个测试用例, 在一行上输出 C(n,k). 你可以假设这个数小于 264.

Sample Input


1000000000 0
163 5

Sample Output


1
901289592
我编写的程序是
#include<iostream>
using namespace std;
int main()
{
    int n,k;
    int sum=1,m=1;        int comm(int n,int k);
    while(cin>>n>>k)
    {cout<<comm(n,k)<<endl;}
    system("pause");
    return 0;
}
int comm(int n,int k)
{
   
for(int n;n>k;n--)//计算n（n-1）....(n-k+1)
{  sum*=n;}

for(int t=1;t<k+1;t++)//计算k的阶乘
{  m*=t;}

return sum/m;
}

程序的算法不对，因为我得到的答案总是0；还有测试用例也不对，我对测试用例感到很困惑。
望朋友指点！

[ 本帖最后由 中国可爱小牛 于 2009-5-24 16:37 编辑 ]

daybreakcx

这么久还没人贴第二题代码？那我来献丑了

第二题直接算是肯定会超时的，但是我们考虑题目的条件：答案<=2^64，也就是答案如果按照连乘的话最多是64次乘法（按照每次最小2来乘），换句话说我们考虑c(n,k)=n!/k!/(n-k)!那么k和n-k中必定有一个是很小的（不然乘法次数太多答案肯定溢出）。假设k<n-k的情况下，我们可以把式子换成[（n-k+1）*...*n]/(1*...*k)，此时计算次数就是k，根据前面的推断，k很小。

同时为了考虑周全，防止计算过程中溢出，我们发现我们的最终式子的分子的前i项乘积必定能被分母前i项整除，所以对于一个新的项目，我们可以先乘法后除，这样可以保证增长比较小，同时因为可以整除，假设我们分子为n-k+i，分母就是i了，当前值是ret，那么ret*(n-k+i)必能被i整除，这时候可以先把ret除掉其与i的最大公约数s，则此时i/s必定能被n-k+i整除，这样最后就变成了这样[ret/gcd(ret,i)]*{(n-k+i)/gcd{[i/gcd(ret,i)],n-k+i}}也就是两部分都不超过long long，乘积也不超过long long，这样就保证不溢出了（实际上貌似因为数据不容易出到溢出，所以直接ret=ret*(n-k+i)/i也不溢出，但是这样做安全点）。

空口无凭，如下附上源代码，请大家指正

#include<stdio.h> int n,k; long long gcd(long long x,long long y) {     long long t;     while (t=x%y)     {         x=y;         y=t;     }     return y; } long long comb(int n,int k) {     if (k>n-k) k=n-k;     long long ret=1,s,t;     int i;     for (i=1;i<=k;i++)     {         s=gcd(ret,i);         ret/=s;         t=(n-k+i)/gcd(i/s,n-k+i);         ret*=t;     }     return ret; } int main() {     while (scanf("%d%d",&n,&k)==2)         printf("%lld\n",comb(n,k));     return 0; }

顺带说一句，ACM真的很好玩

中国可爱小牛

谢谢提醒，我改过来了。
另外，不是说很菜就没有接触ACM的权利和自由，我知道我确实不能在这条路走得远，但也很希望能解决一些相当简单的ACM题目啊。如果你不能为我加油的话，那我还是会给自己鼓励，加油。

daybreakcx

第一题像你那么做就繁琐了，这是个规律题，根本不用算，规律是5后n-1个0再5再n-1个0，该这么来：

#include<stdio.h> int i,n; int main() {     while (scanf("%d",&n)==1)     {         printf("5");         for (i=0;i<n-1;i++) printf("0");         printf("5");         for (i=0;i<n-1;i++) printf("0");         printf("\n");     }     return 0; }

daybreakcx

第二题按照你那么做必然是超时的！有个方法是把n!，k!和(n-k)!分别质因数分解，然后用质因子次数去减最后再乘起来，常规数论题

中国可爱小牛

原帖由 daybreakcx 于 2009-5-24 16:40 发表
第一题像你那么做就繁琐了，这是个规律题，根本不用算，规律是5后n-1个0再5再n-1个0，该这么来：
#include
int i,n;
int main()
{
    while (scanf("%d",&n)==1)
    {
        printf("5");
         ...

觉得你好强！测试成功了，谢谢！

中国可爱小牛

原帖由 daybreakcx 于 2009-5-24 16:44 发表
第二题按照你那么做必然是超时的！有个方法是把n!，k!和(n-k)!分别质因数分解，然后用质因子次数去减最后再乘起来，常规数论题

从数学上说我知道。但我的不足是不能很好地把它表现在程序中.....

daybreakcx

你要说你的第二题如下几个问题：
1、你的sum和m初始化容易导致无效，因为其作用域只在main函数里，如果你要算多case的话拉到全局去
2、你的计算过程有错，因为你的第一个循环其实计算的不是你那个表达式的值，而是n乘到k+1，自己可以看清楚，这样逻辑就错了
3、你的第一个循环中int n就重新定义了一个变量n了，那么原先传入的n就无效了，结果依然是错的
暂时看到这么多，自己改改吧，至于超时改进算法是以后的事情了

浮藻

计算C(N,k)，可以采用数组的方式，分子数组为n*(n-1)*...*(n-k+1),分母数组为k!,用分子去除分母每个数直到为素数为止，最后相乘分子（此时分母均为1）