中国剩余定理:”有物不知几何,三三数余一,五五数余二,七七数余三,问物有几何?“
编程求1000以内的所有解。
小白求教大神如何编程实现这个问题
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- 昏晓错星辰 2017-03-16 10:27关注
//中国剩余定理#include struct node {int divisor; //表示除数int remainder; //表示余数}T[1000];//求最大公约数int gcd ( int n, int m){ return m ? gcd(m, n%m) : n;}int main( ){ //MAX_NUM表示的是所求的解的范围的最大值,MIN_NUM表示所求的解的范围的最小值, //n表示的是同于方程的个数,m表示的是三个除数的乘积,gcd_max表示的是两个数的最大公约数,因为三个除数是互素的 //所以gcd_max=1; int i, j, n, t = 0,m = 1, sum = 0, gcd_max = 0, MAX_NUM, MIN_NUM; printf("请输入有几个方程:\n"); //如上题韩信点兵。输入3 scanf("%d", &n); printf("请输入每组数据( 余数 除数):\n"); // 3 2 5 4 7 6 for ( i = 0; i < n; i++) scanf("%d%d",&T[i].remainder,&T[i].divisor ); printf("请输入所求值的值域:min max\n" ); scanf("%d%d",&MIN_NUM, &MAX_NUM);//求出三个除数的乘积m for ( i = 0; i < n; i++) { gcd_max = gcd (T[i].divisor, gcd_max); m = m * T[i].divisor; } gcd_max *= m;//求mI for ( i = 0; i < n; i++) { t = 0;m = 1; for ( j = 0; j < n; j++) { if (j != i ) { t = gcd( T[j].divisor , t); m = m * T[j].divisor; } } t = m * t; m = t; while (m % T[i].divisor != 1) m += t; sum += m * T[i].remainder; } printf("最小的值为:\n"); printf("%d\n",sum % gcd_max); printf("在所求的值域内值:\n"); if (sum >= MIN_NUM && sum <= MAX_NUM) { sum-=gcd_max; while(sum>=MIN_NUM && sum<=MAX_NUM) { printf("%d ",sum); sum += gcd_max; } }else{ printf("No Solution!\n"); } return 0;}
解决 无用评论 打赏 举报
悬赏问题
- ¥60 版本过低apk如何修改可以兼容新的安卓系统
- ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
- ¥50 有数据,怎么建立模型求影响全要素生产率的因素
- ¥50 有数据,怎么用matlab求全要素生产率
- ¥15 TI的insta-spin例程
- ¥15 完成下列问题完成下列问题
- ¥15 C#算法问题, 不知道怎么处理这个数据的转换
- ¥15 YoloV5 第三方库的版本对照问题
- ¥15 请完成下列相关问题!
- ¥15 drone 推送镜像时候 purge: true 推送完毕后没有删除对应的镜像,手动拷贝到服务器执行结果正确在样才能让指令自动执行成功删除对应镜像,如何解决?