第一次写运算符重载。。

除法直接二分结果（我比较猥琐）

数据太大了，肯定要高精度！！！！！！！！！！！！！！！！！

即使用Qword直接gcd也只能得50分！！！！！！！！！！！！！

题号 　　P1047

类型(?) 　　数论 / 数值

通过 　　313人

提交 　　3956次

通过率 　　8%

变态题高精加、高精减、高精乘、高精MOD、高精DIV，怪不得froger大牛有393行，而且只有8%的通过率

Var

a,b,c,e,f,g:Int64;

Begin

Readln(a,b);

e:=a;f:=b;g:=0;

c:=0;c:=a Mod b;

While c0 Do

Begin

a:=b;

b:=c;

c:=a Mod b;

End;

e:=e Div b;

f:=f Div b;

g:=e*f*b;

Writeln(g);

End.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 07：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 08：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 09：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 10：运行时错误...| 错误号: 106 | 无效数字格式

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

求高手帮忙看看哪儿错了,谢!

直接高精度加GCD递归是不可以的，有3个数据说202错误………………

郁闷了我5次才AC

终于过了!!!!!

我的高精度除法阿~~~

把a*b/gcd(a,b)改成 a/gcd(a,b)*b 再优化了半天才过的..

模板的力量！！

var c,e,f,g:longint;

　　a,b,d,h:qword;

begin

readln(e,f);

a:=e;

b:=f;

d:=a-1;

repeat

　　d:=d+1;

　　if (d mod a=0) and (d mod b =0) then begin

　　 writeln(d);

　　 break;

　　end;

until d=a*b;

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|

怎么会是难度2~~~的题~~~

惊人的通过率...

---|---|---|---|---|---|--

Flag 　　Accepted

题号 　　P1047

类型(?) 　　数论 / 数值

通过 　　270人

提交 　　3252次

通过率 　　8%

难度 　　2

---|---|---|---|---|---|

第270个

以为100位乘100位只有200位，开了200的数组，WA了。。。改1000，就AC。

lcm(a,b)=a*b div gcd(a,b)

gcd(a,b)=gcd(b,a mod b)

再加上高精度除法就能AC了。

个人觉得用这题用更相减损法比辗转相除要好那么一点点...

对于两个数a,b

若a,b都是偶数,则两个同时除2

若a是偶数,则a除2

若b是偶数,则b除2

然后如果a>b,则a := a - b

否则b := b - a

重复上述过程直到a=b(注意要记下每一步的操作)

ans := a(或b)

此时的a(或b,一样)就是原来的gcd ( a , b )

将a , b 都变成1

然后从后向前除了的同时除2的操作不管外

进行逆操作(即原来除的现在乘,原来减的现在加)

再得到新的a,b

此时的gcd ( a , b ) = 1

然后ans := ans * a * b * 2 ^ k就行了

其中k是先前两数同时除2的次数

这样的话可以就避免写高精度除高精度和取模了

var

i,j,ans:qword;

function try(a,b:qword):qword;

begin

if b=0 then try:=a

else try:=try(b,a mod b);

end;

begin

read(i,j);

ans:=try(i,j);

ans:=(i*j) div ans;

writeln(ans);

end.

#include"stfio.h"

main()

{int i,n,m;

scanf("%d%d",&m,&n);

for(i=m;i

一遍AC。全当练练高精度除法。

program gongbei(input,output);

var

a,b,s:integer;

begin

readln(a,b);

已知m,n均为正整数

（1） 计算m*n的积，送临时变量r。

（2） 若m等于n，则输出最小公倍数r/m，算法结束。

（3） 若m大于n，计算m-n，结果送m，否则，计算n-m，结果送n。

（4） 转到（2）或者（3）。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

事实再次说明算法才是解决问题效率的关键。

前几天看了matrix67大牛的一篇文章，讲的是不断的扩大较小数来求最小公倍数，结果就这么编了。。。。。只过3组数据。

然后拼命优化高精度，。。。。过4组数据。

然后从网上下了个高精度，再加上除法辅助。。。。。过5组数据

然后开始想以前怎么求最小公倍数的了，突然想到了：ab最小公倍数＝a*b/最大公约数！！！！！！！

辗转相除法求GCM然后一个高精度乘一个高精度除，秒杀。。。。。

遇到超时的时候一定要想一想算法，往往都是算法不够高校导致了超时。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 07：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 08：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 09：运行时错误...| 错误号: 106 | 无效数字格式

├ 测试数据 10：运行时错误...| 错误号: 106 | 无效数字格式

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

var

i,j,ans:qword;

function try(a,b:qword):qword;

begin

if b=0 then try:=a

else try:=try(b,a mod b);

end;

begin

read(i,j);

ans:=try(i,j);

ans:=(i*j) div ans;

writeln(ans);

end.

Flag 　　 Unaccepted

题号 　　P1047

类型(?) 　　数论 / 数值

通过 　　245人

提交 　　2754次

通过率 　　9%

难度 　　2

提交 讨论 题解