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
提交代码: 非本测试状态的提交人,不能查看程序源代码。
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;
}
我的程序 秒了
没有仔细看楼主的程序,不过,同余貌似不能两边同除吧。
就是这里: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……的原因了