韩信点兵算法怎么才能不超时，求给个思路或者算法 - 编程论坛

#2

azzbcc2013-04-29 10:00

这个思路你试试：

a[0..7] = 2 3 ... 19
m[0..7] = 1 1 ... 1
s[0..7] = 0 0 ... 0
all = a[0] *...*a[7];

s[i]:
  tmp = all / a[i];
  for (n = tmp * 2;;n+=tmp)
    if (m[i] == n % a[i])  break;
  s[i] = n;

result:
  tmp = (s[0] +...+ s[7]);//这里要考虑溢出
  result = tmp % all;

[ 本帖最后由 azzbcc 于 2013-5-1 16:06 编辑 ]

#3

骑猪闯天下2013-04-29 11:15

回复 2楼 azzbcc

#include<stdio.h>
#include<math.h>
main()
{    double x=0,a[8][3],s=1,k,flag;
      int i;
    for(i=0;i<8;i++){scanf("%lf",&a[i][0]);s=s*a[i][0];}
    for(i=0;i<8;i++) scanf("%lf",&a[i][1]);
    for(i=0;i<8;i++)
    {
        for(k=1;;k++)
            if(fmod(((s/a[i][0])*k),a[i][0])==a[i][1]) {a[i][2]=(s/a[i][0])*k; break;}
    }

    for(i=0;i<8;i++)
       x=x+a[i][2];
    x=fmod(x,s);

    flag=0;
    for(i=0;i<8;i++)
        if(x<a[i][0]) {flag=1;break;}
    if(flag==1) x=x+s;

    printf("%.0lf",x);
}
找到个答案就是用的你那个思路，但是
for(i=0;i<8;i++)
       x=x+a[i][2];
    x=fmod(x,s);
这段代码的功能还是不太清楚啊，能给说明一下么

#4

azzbcc2013-04-29 12:21

这段代码就是求result过程，fmod是double求模，不过这道题，用double可以？

#5

骑猪闯天下2013-04-29 14:15

回复 4楼 azzbcc

为什么把8个数+起来再对s求模就能得到想要的结果？
我想知道这是什么思想啊= =，主要是看不懂思想，代码的基本作用还是知道的，就是不知道为什么8个数+起来再对s求模就能得到想要的结果？

#6

azzbcc2013-04-29 19:49

s[i]满足：模a[i]等于m[i]，且能被a[j]（j!=i）整除

所以a[i]能整除s[j]，即s[i]+s[j]模a[i]等于m[i]

#7

骑猪闯天下2013-04-30 08:41

回复 6楼 azzbcc

太感谢了，我明白了