UVA11549计算机谜题

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2544

【题目描述】：

有一个计算器，只能显示n位数字，给定初始数字k和位数n，做无数次的k^2运算，记录每次的k^2的前n位数字，并将这个新的数字做为下次平方的对象。记录在这无数次运算中，出现的最大的n位数字。

【思路分析】：

这道题目在经验之下，应该看出是存在循环节的，反而观之，在大学生数学水平下，不可能直接找到结果的分布。

所以问题就转化成了一道模拟题，因为以前没用过set，所以写了这道比较水的题。

【注意事项】：

循环结不一定又回到初始的k，这点我想错了；

显示前n位不是后n位，所以传统的取模运算失效，应该按位读取每个数，才方便运算；

【重点】：对过程的模拟是难点

【完整代码】：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<math.h>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #include<map>
11 #define MAXN 100000+5
12 #define MAXM 20000+5
13 #define oo 9556531
14 #define eps 0.000001
15 #define PI acos(-1.0)//这个精确度高一些
16 #define REP1(i,n) for(int i=0;i<=(n);i++)
17 #define REP2(i,n) for(int i=1;i<=(n);i++)
18 #define LL long long
19 using namespace std;
20 
21 LL getnext(int n,LL k)//返回k^2的最多前n位
22 {
23     int digit[55],cnt=0;
24     LL k2=k*k;
25     while(k2>0){digit[cnt++]=k2%10;k2=k2/10;}//从低位向高位存储
26     if (cnt<n) n=cnt;//返回前n位;//防止溢出
27     LL ans=0;
28     for(;n;n--)
29     {
30         ans=ans*10+digit[--cnt];
31     }
32     return ans;
33 }
34 set<LL>s;
35 int cas,n;
36 LL k;
37 int main()
38 {
39     cin>>cas;
40     for(;cas;cas--)
41     {
42         cin>>n>>k;
43         s.clear();
44         LL ans=k;s.insert(k);
45         for(;;)
46         {
47             LL nk=getnext(n,k);
48             if (s.count(nk)) break;
49             s.insert(nk);
50             ans=max(ans,nk);
51             k=nk;
52         }
53         cout<<ans<<endl;
54     }
55     return 0;
56 }

【拓展学习】: set的内部函数原理和使用

【little from】：

平衡二叉树实现,所以查找、插入、删除都是O(log2(N))

begin() 　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html