空降题目处(外网)
点我点我点我
空降题目处(内网)
点我点我点我
Description
给出一个整数 ,你可以对 进行两种操作。
1、将x变成4x+3
2、将x变成8x+7
问,最少通过多少次操作,使得x是1000000007的倍数?
Input
一行,一个整数x(1<=x<=1000000006)。
Output
一行,表示最少的操作步数。保证答案不超过10^5。
Solution
16ms(C++)
Bfs+Hash判重.
什么?!你不会Hash?
“自行脑补”——某晗。
2ms(C++)
某晗推出的公式?
一行AC?!
Code
C++ 16ms
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,h[400000],d[400000],w[400000];
bool hash(int x);
int Bfs(int x);
int main()
{
scanf("%d",&x);
printf("%d",Bfs(x%1000000007));
}
bool hash(int x)
{
int y=x%399989;
while ((h[y]!=0)&&(h[y]!=x))
{
y++;
if (y>399989)
y=0;
}
if (h[y]==0)
{
h[y]=x;
return true;
}
else
return false;
}
int Bfs(int x)
{
int i=0,j=1;
long long t;
d[1]=x;
w[1]=0;
while (i<j)
{
i++;
t=((long long)(d[i])*4+3)%1000000007;
if (t==0)
return w[i]+1;
if (hash((int)(t)))
{
j++;
w[j]=w[i]+1;
d[j]=(int)(t);
}
t=((long long)(d[i])*8+7)%1000000007;
if (t==0)
return w[i]+1;
if (hash((int)(t)))
{
j++;
w[j]=w[i]+1;
d[j]=(int)(t);
}
}
}
Pascal 16ms+
uses
math;
var
x:longint;
h,d,w:array [0..400000] of int64;
function hash(x:longint):boolean;
var
y:longint;
begin
y:=x mod 399989;
while (h[y]<>0) and (h[y]<>x) do
begin
inc(y);
if y>399989 then
y:=0;
end;
if (h[y]=0) then
begin
h[y]:=x;
exit(true);
end else
exit(false);
end;
function Bfs(x:longint):longint;
var
i,j:longint;
t:int64;
begin
i:=0;
j:=1;
d[1]:=x;
w[1]:=0;
if (hash(x)) then;
while i<j do
begin
inc(i);
t:=(d[i]*4+3) mod 1000000007;
if t=0 then
exit(w[i]+1);
if (hash(t)) then
begin
inc(j);
w[j]:=w[i]+1;
d[j]:=t;
end;
t:=(d[i]*8+7) mod 1000000007;
if t=0 then
exit(w[i]+1);
if (hash(t)) then
begin
inc(j);
w[j]:=w[i]+1;
d[j]:=t;
end;
end;
end;
begin
readln(x);
writeln(Bfs(x mod 1000000007));
end.
C++ 2ms
#include<cstdio>
using namespace std;
int x,s;
int main(){
for(scanf("%d",&x);x!=0;x=((x<<1)|1)%1000000007)s++;
printf("%d",s%3==0?s/3:s/3+1);
}
Pascal 2ms
const p=1000000007;
var x,c:longint;
begin
readln(x); c:=0;
while (x<>0) or ((x=0) and (c=1)) do begin
inc(c); x:=(x+x+1) mod p;
end;
x:=c div 3; dec(c,x*3);
if c>0 then inc(x);
writeln(x);
end.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)