九度OJ 1085：求root(N, k) （迭代）-白红宇

九度OJ 1085：求root(N, k) （迭代）

阅读量：4206 次

发布时间：2019-05-26

本文共 1001 字，大约阅读时间需要 3 分钟。

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：1407

解决：523

题目描述：

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

样例输出：

来源：

思路：

计算复杂度是O(n)的，如果是n2就会超时。

另外注意用long long，int可能不够。

代码：

#include 
   
     long long root(long long x, int y, int n){    long long a = 1;    while (y)    {        if (y&1)            a = (a*x)%n;        x = (x*x)%n;        y >>= 1;    }    if (a == 0)        a = n;    return a;} int main(void){    int x, y, k;     while (scanf("%d%d%d", &x, &y, &k) != EOF)    {        printf("%lld\n", root((long long)x, y, k-1));    }     return 0;}/**************************************************************    Problem: 1085    User: liangrx06    Language: C    Result: Accepted    Time:10 ms    Memory:912 kb****************************************************************/

转载地址：http://eyeli.baihongyu.com/

你可能感兴趣的文章