讨论 / 我为什么错???????
OI帝国 2010-07-30 21:24:00
点我顶贴 收藏 删除
var n,k:longint;

y:qword;

function f(n:longint):qword;

begin

if n=0 then begin f:=1;exit;end;

y:=f(n div 2)mod k;

y:=y*y mod k;

if n mod 2=1 then y:=y*3 mod k;

f:=y;

end;

begin

read(n,k);

write((f(n-1)+1+k)div 2);

end.

状态: Unaccepted

测评机: Xeost[5]

得分: 80分

提交日期: 2008-9-24 22:45:00

有效耗时: 482毫秒

测试结果1: 通过本测试点|有效耗时156:ms

测试结果2: 通过本测试点|有效耗时46:ms

测试结果3: 通过本测试点|有效耗时46:ms

测试结果4: 通过本测试点|有效耗时47:ms

测试结果5: 通过本测试点|有效耗时46:ms

测试结果6: 通过本测试点|有效耗时47:ms

测试结果7: 测试结果错误.错误结果为:2179

正确结果应为:899

测试结果8: 通过本测试点|有效耗时47:ms

测试结果9: 通过本测试点|有效耗时47:ms

测试结果10: 测试结果错误.错误结果为:12840

正确结果应为:5280

提交代码: 非本测试状态的提交人,不能查看程序源代码。

#1 OI帝国@2008-09-24 08:22:00
回复 删除
顶,

LS复制多了一点...

#2 OI帝国@2008-09-24 08:23:00
回复 删除

我可是下了血本的!!!

#3 OI帝国@2008-09-24 21:20:00
回复 删除

#4 wwww@2008-09-26 21:47:00
回复 删除
#5 蒋介石@2008-09-27 06:49:00
回复 删除
#include <iostream>

using namespace std;

long long n, k;

int main()

{

cin >>n >>k;

long long sum, t=3;

if (n%2==0) sum =1;

else sum = 3;

k = 6 *k;

while (n >>= 1)

{

t= t * t % k;

if (n & 1)

sum = sum * t % k;

}

cout <<(sum+3)/6 <<endl;

return 0;

}

我的程序 秒了

#6 xyshh94225@2010-07-30 21:24:00
回复 删除
回复 楼主OI帝国 的帖子

没有仔细看楼主的程序,不过,同余貌似不能两边同除吧。

就是这里:write((f(n-1)+1+k)div 2);

2m≡a(mod k)不能推出m≡a/2(mod k).

但2m≡a(mod 2k)就可以推出m≡a/2(mod k)了。

这就是为什么一开始要把k变成2k,4k……的原因了

查看更多回复
提交回复