相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人、17人一列余2人、19人一列余10人、23人一列余1人、29人一列余11人。但限时为500ms,我超时很多次都不行，即输入3 5 7 13 17 19 23 29它们分别被余数为1 2 4 6 2 10 1 11输出总兵士数，要求输出满足条件的最小的一个，但要满足8种排法的每一种排法至少可排一列。（保证给的数据，有结果且计算的结果不会超过2的63次方）

#include <stdio.h>

int main()
{
 /*  long long N=1000000000000000000;*/
   int a[8],b[8];
   int i,n;
   for(i=0;i<8;i++)
    scanf("%d",&a[i]);
   for(i=0;i<8;i++)
    scanf("%d",&b[i]);
   for(n=100;;n++)
   {
        if(n%a[0]==b[0])
        if(n%a[1]==b[1])
        if(n%a[2]==b[2])
        if(n%a[3]==b[3])
        if(n%a[4]==b[4])
        if(n%a[5]==b[5])
        if(n%a[6]==b[6])
        if(n%a[7]==b[7])
        break;
   }
   printf("%d",n);
    return 0;
}
检测时显示超时,有没有更好的方法呢?

120ms：

int main()
{
    /*  long long N=1000000000000000000;*/
    int n = 98;
    for (;;)
    {
        if ((n % 29 == 11) && (n % 23 == 1) && (n % 19 == 10) && (n % 17 == 2) && (n % 13 == 6) && (n % 7 == 4) && (n % 5 == 2) && (n % 3 == 1))
        {
            printf("%d", n);
            break;
        }   
        n +=29;
    }   
    return 0;
}

输入格式
要求由键盘输入A,B,C,D,E,F,G,H,a,b,c,d,e,f,g,h十六个数，分别代表每A人一列余a、每B人一列余b、每C人一列余c、每D人一列余D、每E人一列余e、每F人一列余f、每G人一列余g、每H人一列余h，其中A,B,C,D,E,F,G,H为互不相等的质数

忘了说了,这个数字都是要键盘输入的,并不是只要满足一组就可以的

输入样例
2 3 5 7 11 13 17 19
1 1 1 1 1 1 1 1


输出样例
9699691

下面的超时否？

#include<stdio.h>

int main()
{
    int a[8]={0},b[8]={0};    
    int i=0;
    unsigned long long l;
    
    for(;i<8;i++)
    {
        scanf("%d",&a[i]);
    }
       
    for(i=0;i<8;i++)
    {
        scanf("%d",&b[i]);
    }

    for(l=a[7]+b[7];;l+=a[7])
    {
        if(l%a[0]!=b[0])   continue;
        if(l%a[1]!=b[1])   continue;
        if(l%a[2]!=b[2])   continue;
        if(l%a[3]!=b[3])   continue;
        if(l%a[4]!=b[4])   continue;
        if(l%a[5]!=b[5])   continue;
        if(l%a[6]!=b[6])   continue;
        break;
    }
    
    printf("%I64u\n",l);
    
    return 0;
}

[此贴子已经被作者于2016-3-16 13:21编辑过]

就是那个意思，改一下一样。
#include <stdio.h>

int main()
{
    /*  long long N=1000000000000000000;*/
    int a[8], b[8];
    int i, n;
    for (i = 0; i<8; i++)
        scanf("%d", &a[i]);
    for (i = 0; i<8; i++)
        scanf("%d", &b[i]);
    n = a[7] + b[7];
    for (;;)
    {
        if ((n % a[6] == b[6]) && (n % a[5] == b[5]) && (n % a[4] == b[4]) && (n % a[3] == b[3]) && (n % a[2] == b[2]) && (n % a[1] == b[1]) && (n % a[0] == b[0]))
        {
            printf("%d", n);
            break;
        }   
        n +=a[7];
    }   
    return 0;
}

设除数为：d1 d2 d3 ... d8  最小公倍数为D
  余数为：r1 r2 r3 ... r8

给你两个思路：
1. 用剩余定理
  设Di 为 d1 d2 ... di-1 di+1 ... d8的最小公倍数

  有解 n = D1 * r1 + D2 * r2 + ... + D8 * r8 + kD (k 为任意整数)

2. 简化一下方法1
遍历 1-D，必有解。

oj直接检测错误

显示超时啊

中国剩余定理
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
  clock_t pre,aft;
  pre=clock();
  int Ext_Enuclidean(int ,int);  /*应用扩展欧几里得算法*/
  int a1,b1,c1,d1,e1,f1,g1,h1,a2,b2,c2,d2,e2,f2,g2,h2,y1,y2,y3,y4,y5,y6,y7,y8;
  long long s;
  scanf("%d%d%d%d%d%d%d%d",&a1,&b1,&c1,&d1,&e1,&f1,&g1,&h1);
  /*if((a<0&&a>=3)||(b<0&&b>=5)||(c<0&&c>=7)){
      printf("No answer\n");
      return;
  }*/

  scanf("%d%d%d%d%d%d%d%d",&a2,&b2,&c2,&d2,&e2,&f2,&g2,&h2);
  if(a2>a1||b2>b1||c2>c1||d2>d1||e2>e1||f2>f1||g2>g1||h2>h1){
    printf("No answer\n");
    return 1;
  }
  int M,M1,M2,M3,M4,M5,M6,M7,M8;
  M=a1*b1*c1*d1*e1*f1*g1*h1;
  M1=b1*c1*d1*e1*f1*g1*h1;
  M2=a1*c1*d1*e1*f1*g1*h1;
  M3=a1*b1*d1*e1*f1*g1*h1;
  M4=a1*b1*c1*e1*f1*g1*h1;
  M5=a1*b1*c1*d1*f1*g1*h1;
  M6=a1*b1*c1*d1*e1*g1*h1;
  M7=a1*b1*c1*d1*e1*f1*h1;
  M8=a1*b1*c1*d1*e1*f1*g1;
  y1=Ext_Enuclidean(a1,M1);
  y2=Ext_Enuclidean(b1,M2);
  y3=Ext_Enuclidean(c1,M3);
  y4=Ext_Enuclidean(d1,M4);
  y5=Ext_Enuclidean(e1,M5);
  y6=Ext_Enuclidean(f1,M6);
  y7=Ext_Enuclidean(g1,M7);
  y8=Ext_Enuclidean(h1,M8);
  if(y1<0||y2<0||y3<0||y4<0||y5<0||y6<0||y7<0||y8<0){
      printf("No answer\n");
      return 1;
  }
  s=M1*y1*a2+M2*y2*b2+M3*y3*c2+M4*y4*d2+M5*y5*e2+M6*y6*f2+M7*y7*g2+M8*y8*h2;
  /*printf("s=%d\n",s);*/
  s%=M;
  if(s<0||s>pow(2,63))
     printf("No answer\n");
  else
     printf("%d\n",s);
  aft=clock();
  printf("clock time=%d\n",aft-pre);
}
int Ext_Enuclidean(int pa1,int pa2)  /*这里计算乘法逆元*/
{
  if(pa1>pa2){  /*交换后pa2为较大的数*/
    int tmp=pa1;
    pa1=pa2;
    pa2=tmp;
  }
  int x1,x2,x3,y1,y2,y3,t1,t2,t3;
  x1=1,x2=0,x3=pa2,y1=0,y2=1,y3=pa1;
  while(y3>1){
    int q=x3/y3;
    t1=x1-q*y1,t2=x2-q*y2,t3=x3-q*y3;
    x1=y1,x2=y2,x3=y3;
    y1=t1,y2=t2,y3=t3;
  }
  if(y1<0)
     y1+=pa1;
  if(y3==1)
     return y1;  /*y1为乘法逆元*/
  else
     return -1;
}

[此贴子已经被作者于2016-3-16 14:04编辑过]