编译通过...

├ 测试数据 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

提交 讨论 题解

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

无比郁闷,,,本来应该一次AC的`\

谁知

READLN(S1);

READLN(S2);

寒到了,,,全部超时无输出,,,觉得不对呀,,,然后第一感觉评测机抽风``

再交一次还错`- - 后来发现只有一行读入

不难.80行够了..

疯狂的题目……写了200多行才对4个点……

1次AC，奇迹奇迹。

最小公倍数=a*b/最大公约数

crazy

program aa;

var temp,a,b,n,m,c,d:int64;

begin

readln(a,b);

if b>a then begin

n:=b;

m:=a;

c:=b;

d:=a;

end

else begin

n:=a;

m:=b;

c:=a;

d:=b;

end;

while true do begin

if n mod m=0 then break;

temp:=n;

n:=m;

m:=temp mod m;

end;

writeln((c div m) *d);

end.

第九个点很麻烦吗？我只有它花了41ms，别的都是0ms