首页 > 试题广场 >

求root(N, k)

[编程题]求root(N, k)
  • 热度指数：18232 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    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)的值
示例1

输入

4 4 10

输出

4
算法知识视频讲解
开通博客
头像 wbc990512
发表于 2021-01-23 17:04:27
①首先是由于x^y可能很大，会超时，所以用快速幂算法。如果y是偶数，那么指数减半底数平方；如果y是奇数，那么给最终的结果乘上x的一次方，这样能够求出x^y的结果res。②再来看root（N，k），根据题意有N = a0 + a1*k + a2*k^2 +...N' = a0 + a1 + a2+ . 展开全文
去ta的博客 赞 (65) 回复(8) 收起
头像 philos
发表于 2021-02-04 17:34:43
思路 乘方可以使用乘法快速幂，可以看看我在 leetcode 上的题解。 因为可能会溢出 int，那么我们使用 long long 对于root（N，k），根据题意有 同理可得 ，依次类推， 因为最后 ，所以，如果，说明 #include<iostream> using names 展开全文
去ta的博客 赞 (15) 回复(0) 收起
头像 _Abyss_
发表于 2023-03-15 20:06:32
//root(N, k) = N % (k - 1) #include <stdio.h> typedef long long LL; LL fast_pow(LL a, LL b, int mod) { LL res = 1; while(b > 0) { 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 牛客652687585号
发表于 2022-03-06 14:47:16
#include<iostream> #include<cstdio> using namespace std; int QuickPower(int x,int y,int n){    展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 宁静的冬日
发表于 2022-03-09 13:53:43
root(N,k)=root(Nd,k);其中Nd=N%（k-1） #include<iostream> using namespace std; #include<algorithm> #include<cstring> #include<string&g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 flyflyfly00
发表于 2021-03-23 09:55:41
原本想这样模拟过程但是这样太复杂。需要思考别的方法~ #include <iostream> #include <cstdio> #include <vector> using namespace std; bool Judge(vector<int&g 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 JavaGPT
发表于 2022-02-17 16:20:34
#include<iostream> using namespace std; long root(long x,long y,int k){     int result=1;     while(y!=0){     & 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 JianJ
发表于 2024-03-02 17:09:54
#include<iostream> typedef long long LL; using namespace std; int qpow(LL x,LL y,LL k) { if(y == 0) return 1; if(y % 2 == 0) { LL temp = qp 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 土尔逊Torson
发表于 2023-05-18 01:50:57
//土尔逊Torson 编写于2023/05/18 #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> using namespace std; long long MyPow(lon 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ManoCode
发表于 2024-09-02 23:29:15
#include <bits/stdc++.h> using namespace std; int QuickPower(int x, int y, int n) { //取x^y的n进制的个位数 int ans = 1; while (y) { if ( 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 基础数学 快速幂 递归
难度：
42条回答 14493浏览

热门推荐

通过挑战的用户

查看代码

相关试题

求root(N, k)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号