中国剩余定理:”有物不知几何,三三数余一,五五数余二,七七数余三,问物有几何?“
编程求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;}
解决 无用评论 打赏 举报
悬赏问题
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 ubuntu子系统密码忘记
- ¥15 保护模式-系统加载-段寄存器
- ¥15 电脑桌面设定一个区域禁止鼠标操作
- ¥15 求NPF226060磁芯的详细资料