荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: ACM (ACM), 信区: ACMICPC
标 题: [合集]teacher's nuber 剩余问题与《孙子算法》
发信站: 荔园晨风BBS站 (Wed Mar 31 11:49:28 2004), 站内信件
posidone (海王波赛冬) 于Sat Mar 27 10:04:57 2004提到：
我已经找到此类问题的算法，请看以下网站：
http://www.srsoft.com.cn/study_garden_plot/drkt/drkt/gz_sx/qwsx/0/
算法稍后贴出。
Kenniel (笑翻下先^_^) 于Sat Mar 27 10:24:12 2004提到：
呵呵！当时我就是用这个做了！不过当数
很大的时候就超时，不知道师弟有什么妙法呵呵
selahx (灵犀一指) 于Sat Mar 27 10:38:04 2004提到：
呵呵，好像的确高效很多，但怎样判定无解，还有那题答案有没有上限啊？
kali (江火) 于Sat Mar 27 10:40:20 2004提到：
问题确保有解的！！
呵呵，好像的确高效很多，但怎样判定无解，还有那题答案有没有上限啊？
posidone (海王波赛冬) 于Sat Mar 27 10:41:38 2004提到：
这个算法比起试探法已经优化了很多。
关键的地方，
一个是求最小公倍，另一个就是找乘数ai；
最小公倍是满足结合律的。
只要能求解两个数的最小公倍，就可以求出多个数的最小公倍。
请问：谁有求两数最小公倍的简化算法？请贴一下。
至于ai，是有规律的。
不是死算。
他是观察衍母除m的余数，去计算的。
近一步的算法正在构造中，
肯定可以解出。
posidone (海王波赛冬) 于Sat Mar 27 10:45:28 2004提到：
如果所给数据是无解的，
那谁都没办法。
不过既然题目没说无解的输出要求，
裁判就不会给无解的数据。
justry (乐悠悠) 于Sat Mar 27 10:49:13 2004提到：
调用endid函数可以求公倍数，不过是包含在那个头文件里阿
kaman (天外飞仙) 于Sat Mar 27 10:52:45 2004提到：
无解也应该能判断吧～～～～
6 8 9
1 1 2
8*9％6＝0
用孙子定理就不能算出M了～～
kali (江火) 于Sat Mar 27 10:52:57 2004提到：
int Edild(int a,int b)
{
if(b==0) return a;
return Edild(b,a%b);
}
int smallmul(int a,int b)
{
int temp;
if(a<b){
a=temp;
a=b;
b=temp;
}
return(a*b/Edild(a,b));
}
kali (江火) 于Sat Mar 27 10:54:35 2004提到：
题目的意思是m[i]是互质的！！
无解也应该能判断吧～～～～
6 8 9
1 1 2
8*9％6＝0
用孙子定理就不能算出M了～～
selahx (灵犀一指) 于Sat Mar 27 11:01:28 2004提到：
那个究竟有没有解啊～～～那么？
kali (江火) 于Sat Mar 27 11:06:33 2004提到：
这里m[i]是6 8 9，这是互质？？
像3 7 17 25 26这几个数是一定有解的。
selahx (灵犀一指) 于Sat Mar 27 11:12:15 2004提到：
原题目有没有说是互质的？
justry (乐悠悠) 于Sat Mar 27 11:15:58 2004提到：
原题目说m是两两互质的，求公倍数直接把它们 几个乘起来就好，不用函数了
selahx (灵犀一指) 于Sat Mar 27 11:17:45 2004提到：
呵呵～那就好办多了
huhaiming (一生只爱她) 于Sat Mar 27 18:50:03 2004提到：
最小公倍数直接用最大公约数就可以求拉，很简单的了
//最大公约数
int Enclid(int p,int q)
{
if(q==0) return p;
else return Enclid(q,p%q);
}
//最小公倍数
int LCM(int p,int q)
{
return p*q/Enclid(p,q);
}
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店