首页 > 代码库 > 九度oj 题目1085:求root(N, k) 清华2010年机试题目
九度oj 题目1085:求root(N, k) 清华2010年机试题目
- 题目描述:
N<k时,root(N,k) = N,否则,root(N,k) = root(N‘,k)。N‘为N的k进制表示的各位数字之和。输入x,y,k,输出root(x^y,k)的值 (这里^为乘方,不是异或),2=<k<=16,0<x,y<2000000000,有一半的测试点里 x^y 会溢出int的范围(>=2000000000)
- 输入:
每组测试数据包括一行,x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)
- 输出:
输入可能有多组数据,对于每一组数据,root(x^y, k)的值
- 样例输入:
4 4 10
- 样例输出:
4
这道题我苦思冥想了很久,最令我头疼的就是数据的范围,2000000000的2000000000次方该有多大,如何去计算?
每次都要求N的k进制表示的各位数字之和,那么一要取模,二要求除法,这么大的数怎么做。题目考的一定不是大数的运算,肯定存在某种规律,那么这种规律是什么?
在思考的过程中,首先考虑了 1. (a*b)mod N = (a * (b mod N)) mod N;
其次也考虑到了每次都要求N的k进制表示的各位数字之和,那么最后的那个和就是 2. N mod (k-1) (这个是凭找规律看出来的)
但接下来自己的思路就比较混乱,不知道该怎么处理x的y次方的问题,想了很久也没有想出来。
最后忍不住看了看其他人的题解,
他们确实求了x的y次方,而且用的是反复平方法来求,并且在求的过程中直接做取模运算,避免了数据溢出。差距就在这里。
代码如下1 #include <cstdio> 2 #include <cstring> 3 4 typedef long long ll; 5 6 7 int root(ll x, ll y, ll k) { 8 ll mi = 1; 9 while (y) {10 if (y & 1) {11 mi = (mi*x) % k;12 }13 x = (x * x)%k;14 y = y >> 1;15 }16 return mi;17 }18 19 int main() {20 ll x, y, k;21 while (scanf("%lld %lld %lld", &x, &y, &k) != EOF) {22 ll ans = root(x, y, k-1);23 if (ans == 0) {24 ans = k - 1;25 }26 printf("%lld\n", ans);27 }28 return 0;29 }
关于第2点
N=a0+a1*k+a2*k^2+……an*k^n N‘=a0+a1+a2+……+an N-N‘=a1*(k-1)+a2*(k-1)^2+a3*(k-1)^3+......+an*(k-1)^n (N-N‘)%(k-1)=0 (N‘-N‘‘)%(k-1)=0 ..... (N(r-1)-N(r))%(k-1)=0 相加得(N-N(r))%(k-1)=0 N(r)=N%(k-1) 故(x^y)%(k-1)就是我们要求的。 当(x^y)%(k-1)=0时,注意结果为k-1
九度oj 题目1085:求root(N, k) 清华2010年机试题目
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。