题解 - Vijos

0

newdeng LV 8 @ 2009-02-14 10:04:08

忙了整整一天，终于接受了。

思路：假设原数为n,先求个位的循环节，即试探n*n与n个位相等吗？，不等，试试n*(n^2),类推，假设n*(n^x)个位与n相等，试探n*(n^x)的十位与n的十位相等吗？，不等，试试n*((n^x)^2),...假设n*((n^x)^m)的十位与n的十位相同。试探n*((n^k)^m)的百位与n的百位相同吗？不同试探n*（((n^x)^m)^2),......直到所有k位都相等，如果试探１０次都不相等，输出-1.

有问题,问问newdeng就知道

0

linw8 LV 8 @ 2008-12-14 10:12:47

var w,a,b,c:array[0..10000] of longint;

　　st:string;

　　i,j,k,l,m,n,q:longint;

　　perdo,total:longint;

　　tot:array[0..100000] of longint;

procedure mult(t:longint);

var p,i,j:longint;

begin

***|\**|\**|\**|\**|\**|\**|\**|\**|\**|*

end;

procedure doout;

begin

writeln(-1);

halt;

end;

procedure makenew;

begin

a:=b;

mult(perdo-1);

b:=c;

end;

procedure dototal;

var i,j:longint;

begin

for i:=1 to tot[0] do

　　tot[i]:=tot[i]*perdo;

if tot[tot[0]]>9 then inc(tot[0]);

for i:=2 to tot[0]+1 do

begin

　　tot[i]:=tot div 10 + tot[i];

　　tot:=tot mod 10;

end;

end;

begin

readln(st);

n:=pos(' ',st)-1;

val(copy(st,n+2,length(st)-n-1),k,i);

total:=1;

tot[0]:=1;

tot[1]:=1;

for i:=1 to n do

　　a[n-i+1]:=ord(st[i])-48;

w:=a;

c:=w;

b:=a;

for q:=1 to k do

begin

　　perdo:=0;

　　a:=w;

　　repeat

　　 inc(perdo);

　　 if perdo>1 then a:=c;

　　 fillchar(c,sizeof(c),0);

　　 mult(1);

　　until (w[q]=c[q]) or (perdo>10);

　　if perdo>10 then doout;

　　dototal;

　　makenew;

end;

for i:=tot[0] downto 1 do

　　write(tot[i]);

writeln;

end.

0

897639498 LV 6 @ 2008-11-12 20:38:37

编译通过...

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

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

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

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

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

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

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

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

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

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

开始看以为很简单，细看才知道爆难。一天费了。

0

yinger650 LV 8 @ 2008-11-12 18:31:31

题解只给需要的人不是刷题的人

var w,a,b,c:array[0..10000] of longint;

st:string;

i,j,k,l,m,n,q:longint;

perdo,total:longint;

tot:array[0..100000] of longint;

procedure mult(t:longint);

var p,i,j:longint;

begin

***|\**|\**|\**|\**|\**|\**|\**|\**|\**|*

end;

procedure doout;

begin

writeln(-1);

halt;

end;

procedure makenew;

begin

a:=b;

mult(perdo-1);

b:=c;

end;

procedure dototal;

var i,j:longint;

begin

for i:=1 to tot[0] do

tot[i]:=tot[i]*perdo;

if tot[tot[0]]>9 then inc(tot[0]);

for i:=2 to tot[0]+1 do

begin

tot[i]:=tot div 10 + tot[i];

tot:=tot mod 10;

end;

end;

begin

readln(st);

n:=pos(' ',st)-1;

val(copy(st,n+2,length(st)-n-1),k,i);

total:=1;

tot[0]:=1;

tot[1]:=1;

for i:=1 to n do

a[n-i+1]:=ord(st[i])-48;

w:=a;

c:=w;

b:=a;

for q:=1 to k do

begin

perdo:=0;

a:=w;

repeat

inc(perdo);

if perdo>1 then a:=c;

fillchar(c,sizeof(c),0);

mult(1);

until (w[q]=c[q]) or (perdo>10);

if perdo>10 then doout;

dototal;

makenew;

end;

for i:=tot[0] downto 1 do

write(tot[i]);

writeln;

end.

S.Y.F @ 2013-10-29 19:21:01

说的好！

0

IVORY LV 4 @ 2008-11-10 14:08:09

不会写啊

很猥琐地来看题解

......

0

liziqi LV 3 @ 2008-11-07 21:43:02

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

刚开始忘记把fout改成cout...

话说我的AC率就是这样子下降的...

具体题解,我也是看了下面的大牛才做出来的..

倍增思想.+高精度的运算.烦啊....

后面求一个数的X次方的时候,刚开始没用dfs做二分,直接每次除以二来求,结果错了,检查了很久

后面就没什么了...

高精度比较烦而已...

提高耐心....

#include

using namespace std;

struct note

{

int len;

int num[205];

};

note n, ans;

note di, ji, temp;

int k;

void input()

{

string s;

cin >> s;

n.len = s.size();

for (int i = 1; i> k;

for (int i = k+1; i= 1; i--) cout

0

FenXy LV 10 @ 2008-11-04 12:24:55

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

还行吧...

0

jtjxhjl321 LV 3 @ 2008-11-02 16:13:08

第十组一直过不去，原来是把k=100读成k=00了，恶心哪

0

吴豪 LV 8 @ 2008-10-15 00:37:04

主要思路是倍增法。

一开始每次乘原数t，k1次后出现循环

把乘数改成t^k1，算第二位的循环k2

把乘数改成(t^k1)^k2 继续……

过程中如果乘了超过十次就无解……

0

zkkmj LV 8 @ 2008-10-05 17:08:03

编译通过...

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

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

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

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

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

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

├ 测试数据 07：运行时错误...| 错误号: 128 |

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

├ 测试数据 09：运行时错误...| 错误号: 128 |

├ 测试数据 10：运行时错误...| 错误号: 128 |

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

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

?

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

原来128指的是…………………………201

0

lemon_cn LV 3 @ 2008-10-02 11:42:25

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

有点恶心...

普及组还有这么BT的题？

0

玛维-影之歌 LV 10 @ 2008-11-29 21:00:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不错。第500次提交把这题AC了。。。

176/500(35%)

0

月De孤独 LV 3 @ 2008-09-19 13:57:08

经典的倍增法加高精度注意保留我的这个高精度写的偷懒了所以效率比较低.

Program Circle;

Const

Maxn = 300;

Type

Hs = Array [0..Maxn] Of Integer;

Var

G, S, B, R, F, Ans, Ans1: Hs;

A: Array [1..4] Of Integer;

i, j, k, L, p, n, t: Integer;

Str: String;

d, Pd: Boolean;

Procedure HIMul(a: Hs; b: Integer; Var c:Hs);

Var

x, i: Integer;

Begin

x := 0;

FillChar(c, SizeOf(c), 0);

For i:= 1 To 100 Do Begin

c[i] := c[i] + a[i] * b;

c[i + 1] := c[i] Div 10;

C[i] := c[i] Mod 10;

End;

End;

Procedure HHMul(a, b: Hs; Var c: Hs);

Var

x, i, j: Longint;

Begin

x:=0;

FillChar(c, SizeOf(c), 0);

For i:= 1 To 101 Do

For j:= 1 To 101 Do Begin

c[i + j - 1] := c[i + j - 1] + a[i] * b[j];

c[i + j] := c[i + j] + c[i + j - 1] Div 10;

c[i + j - 1] := c[ i + j - 1] Mod 10;

End;

End;

Begin

FillChar(G, SizeOf(G), 0);

FillChar(Ans, SizeOf(Ans), 0);

FillChar(F, SizeOf(F), 0);

F[1] := 1;

ReadLn(Str);

n := Length(Str);

L := Pos(' ', Str);

Val(Copy(Str, L + 1, n - L + 1), k, t);

Dec(L);

For i:= 1 TO L Do G[i] := Ord(Str[L - i + 1]) - 48;

B := G;

Pd := True;

For i:= 1 To k Do Begin

S := G;

FillChar(R, SizeOf(R), 0);

R[1] := 1;

d := False;

For j:= 1 To 10 Do Begin

HHMul(S, B, S);

HHMul(R, B, R);

If S[i] = G[i] Then Begin

Ans1[i] := j;

d := True;

Break;

End;

End;

If d Then B := R Else Begin

Pd := False;

Break;

End;

End;

Ans[1] := 1;

For i:= 1 To k Do HIMul(Ans, Ans1[i], Ans);

L := Maxn;

While (Ans[L] = 0) And (L > 0) Do Dec(L);

If Pd Then Begin

For i:= L DownTo 1 Do Write(Ans[i]);

End Else Write(-1);

End.

0

swxadqecz LV 5 @ 2008-09-12 19:39:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

多年没AC的题……今朝80行拿下……

0

GhostKnight LV 5 @ 2008-08-30 21:44:22

对于每一个N位树...求最后K位数的循环节..........

其实........我们第一次想.....就是直接乘.........只到相等...........

但是..............对于100位的东西............总共有最坏有10^100种选择..............你还会用这个方法吗?

如果你会用............关了这个望网页吧....................................

扯远了

首先.......我们用分治法来分层............从最后一位开始向前分

从万恶的乐乐给出的一位数的循环节可以看出..................这几个数有循环节...........

我们再继续分析.......经常被开刀的2的循环节是 2 4 8 6

那么.......2乘上多少又到了2呢?

2 2*2=4 (舍去)

4 2*4=8 (舍去)

8 2*8=16 (舍去)

16 2*4=8 (舍去)

找到答案了这个数是...........是16..............但是..................啊...............是2^4............是2^循环节

如果每次等乘上16......就可以保证最后一位总是2.............

那么........同理..........以后每到下一层.....................以上一层找到的那个乘数为基准数.......再乘......直到符合循环的要求.............

比如说33 2

先判断最后一位......为了方便直接取K位

先取乘数33........至于为什么.......看题吧.......我也不知道........别问我

33 89 37 21 93 找到了...循环节是4.........那么下一个乘数是 33^4 mod 100=21

再从33开始........这次的乘数是21.......

33 93 53 13 73 33 看.............这个就是答案了........循环节是5

答案就是4*5

最后还有一点.........就是关于非循环节的判断.........

很多人说如果循环过了10次还有可能是循环节...........

我可以证明.......这个说法是错的.........最多10次.........

从上面的分析来看.......到第N位是......前N-1位全部多是固定了的........无论怎么乘.....都是固定的.......()......变的只是第N位

一个数位上只可能有10种填法...............所以.....超过10种.........就不存在了............

应该就这么多了................

CarryH_Y_H @ 2016-11-12 15:42:55

OTZ

0

cgy4ever LV 10 @ 2008-08-28 23:23:12

这题好复杂，写了好半天

0

heping LV 3 @ 2008-08-12 14:23:37

k>20时好像是可以的啊

0

牧云海 LV 10 @ 2008-08-12 13:31:57

vijos的评测机该骂了！！

我同样的程序，连个分号都没改，居然测三次，三个不一样的结果，而且超时的点还不一样，分越来越低！！！

我交了6次，一次还没过呢！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

我的AC率………………

10个百分点！

刚交完第七次，终于A了，我就说我的程序没错！

0

syx7997 LV 3 @ 2008-07-24 20:49:34

楼下的你的程序真能AC吗？

0

asd4823765 LV 9 @ 2007-11-17 09:42:44

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

提交 22 / 50 题 ( 44% )

{44(死死`\``)不太吉利啊赶快再做一题}

题解

104 条题解

循环

信息

状态

开发

支持

题解

104 条题解

循环

信息

状态

开发

支持

还没有账户？

登录