主题：[讨论]请教一道ACM的题
schopenkitto
[专家分：0] 发布于 2006-11-11 08:10:00
一道北美试题，已知函数形如：
f(x)=b^f(x-1);
f(0)=1；
1<x<100;1<b<100；b和x均为整数。
函数值也就是2^(2^(2^2));5^(5^(5^5))之类的大数（嵌套几层由x决定）。
求这样的大数的末几位数字（可取1到7位）。
肯定不能硬算，数字太大。应该是要找尾数循环的规律。需要数论知识了。
哪位大侠能给点思路。
谢过了
[em18]
回复列表 （共5个回复）
沙发
rickone [专家分：15390] 发布于 2006-11-11 22:53:00
取七位太大了吧~~
#include <iostream>
#include <map>
using namespace std;
int resolve(int b,int x,int m)
{
if(m==1)
return 0;
if(x==1)
return b%m;
int *r=new int[m];
map<int,int> rm;
r[0]=b%m;
rm[r[0]]=0;
for(int i=1;;++i)
{
r[i]=(r[i-1]*b)%m;
if(rm.find(r[i])==rm.end())
rm[r[i]]=i;
else
break;
//cout<<r[i-1]<<",";
}
int j=rm[r[i]];
int len=i-j;
int y=resolve(b,x-1,len);
y=(y-1+len)%len;
int result;
if(y<=j)
result=r[y+len];
else
result=r[y];
delete[] r;
return result;
}
int main(void)
{
int b,x,m;
cin>>b>>x>>m;
cout<<resolve(b,x,m)<<endl;
return 0;
}
板凳
rickone [专家分：15390] 发布于 2006-11-11 22:59:00
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int resolve(int b,int x,int m)
{
if(m==1)
return 0;
if(x==1)
return b%m;
vector<int> r;
map<int,int> rm;
r.push_back(b%m);
rm[r[0]]=0;
for(int i=1;;++i)
{
r.push_back((r[i-1]*b)%m);
if(rm.find(r[i])==rm.end())
rm[r[i]]=i;
else
break;
//cout<<r[i-1]<<",";
}
int j=rm[r[i]];
int len=i-j;
int y=resolve(b,x-1,len);
y=(y-1+len)%len;
int result;
if(y<=j)
result=r[y+len];
else
result=r[y];
return result;
}
int main(void)
{
int b,x,m;
cin>>b>>x>>m;
cout<<resolve(b,x,m)<<endl;
return 0;
}
换成vector，时间效率差些，估计空间上没原来那么浪费。差不多效率，感觉。
3 楼
schopenkitto [专家分：0] 发布于 2006-11-13 20:33:00
斑竹还真强啊，这么快出2歌算法了。
实在太感谢了。
4 楼
schopenkitto [专家分：0] 发布于 2006-11-13 21:42:00
如果没理解错。m应该是10^n吧。
int len=i-j;
int y=resolve(b,x-1,len);
y=(y-1+len)%len；
这里len是尾数循环长度，但是这个递归是什么用意，y的算法有什么理论基础没。
答案对，但是想不透里面的玄机，呵呵。
还望不吝赐教了
5 楼
rickone [专家分：15390] 发布于 2006-11-13 22:51:00
就是数论的方法吧，你用手算一下这个题：
7^(7^(7^7))的末两位数是多少？
我来回复
您所在位置：